Accept
YOYO
posted @ 2009年5月12日 18:33
in 【ICPC】解题报告
with tags
计算几何
, 2256 阅读
FJNU2060:http://acm.fjnu.edu.cn/show?problem_id=2060
n^4暴力硬过的 囧。
思路就是,枚举所有可能的线,先判断两线是否重合,不重合再判断是否垂直即可。
-
#include<iostream>
-
#include<cmath>
-
using namespace std;
-
-
#define eps 1e-8
-
#define zero(x) (((x)>0?(x):-(x))<eps)
-
typedef struct{int x,y;}point;
-
typedef struct{point a,b;}line;
-
-
int perpendicular(line u, line v){
-
return zero((u.a.x-u.b.x)*(v.a.x-v.b.x)+(u.a.y-u.b.y)*(v.a.y-v.b.y));
-
}
-
-
bool cmp(point a, point b){
-
return a.x==b.x?a.y==b.y:false;
-
}
-
-
bool cmp(line u, line v){
-
if(u.a.x-u.b.x==0&&v.a.y-v.b.y==0)return false;
-
return ((u.a.x-u.b.x)*(v.a.x-v.b.x)-(u.a.y-u.b.y)*(v.a.y-v.b.y))==0;
-
}
-
-
int main(){
-
int n;
-
while(cin>>n){
-
point p[105];
-
int i,j;
-
for(i=0; i<n; i++){
-
cin>>p[i].x>>p[i].y;
-
}
-
line v,u;
-
bool flag = false;
-
for(i=0; i<n; i++){
-
u.a.x = p[i].x;
-
u.a.y = p[i].y;
-
for(j=i+1; j<n; j++){
-
if(cmp(p[i], p[j]))continue;
-
u.b.x = p[j].x;
-
u.b.y = p[j].y;
-
for(int i1 = 0; i1<n; i1++){
-
v.a.x = p[i1].x;
-
v.a.y = p[i1].y;
-
for(int j1 = i1+1; j1<n; j1++){
-
v.b.x = p[j1].x;
-
v.b.y = p[j1].y;
-
if(cmp(u,v))continue;
-
if(perpendicular(u,v)){
-
flag = true;
-
break;
-
}
-
}
-
if(flag)break;
-
}
-
if(flag)break;
-
}
-
if(flag)break;
-
}
-
cout<<((flag)?"YES":"NO")<<endl;
-
}
-
return 0;
-
}
呼呼~幸好我带了计算几何的模版 = v =
- 无匹配