Liny_@NotePad

沉迷ACG中

Accept

YOYO posted @ 2009年5月12日 18:33 in 【ICPC】解题报告 with tags 计算几何 , 2229 阅读

FJNU2060：http://acm.fjnu.edu.cn/show?problem_id=2060

n^4暴力硬过的 囧。
思路就是，枚举所有可能的线，先判断两线是否重合，不重合再判断是否垂直即可。

  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4.  
  5. #define eps 1e-8
  6. #define zero(x) (((x)>0?(x):-(x))<eps)
  7. typedef struct{int x,y;}point;
  8. typedef struct{point a,b;}line;
  9.  
  10. int perpendicular(line u, line v){
  11.         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));
  12. }
  13.  
  14. bool cmp(point a, point b){
  15.         return a.x==b.x?a.y==b.y:false;
  16. }
  17.  
  18. bool cmp(line u, line v){
  19.         if(u.a.x-u.b.x==0&&v.a.y-v.b.y==0)return false;
  20.         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;
  21. }
  22.  
  23. int main(){
  24.         int n;
  25.         while(cin>>n){
  26.                 point p[105];
  27.                 int i,j;
  28.                 for(i=0; i<n; i++){
  29.                         cin>>p[i].x>>p[i].y;
  30.                 }
  31.                 line v,u;
  32.                 bool flag = false;
  33.                 for(i=0; i<n; i++){
  34.                         u.a.x = p[i].x;
  35.                         u.a.y = p[i].y;
  36.                         for(j=i+1; j<n; j++){
  37.                                 if(cmp(p[i], p[j]))continue;
  38.                                 u.b.x = p[j].x;
  39.                                 u.b.y = p[j].y;
  40.                                 for(int i1 = 0; i1<n; i1++){
  41.                                         v.a.x = p[i1].x;
  42.                                         v.a.y = p[i1].y;
  43.                                         for(int j1 = i1+1; j1<n; j1++){
  44.                                                 v.b.x = p[j1].x;
  45.                                                 v.b.y = p[j1].y;                               
  46.                                                 if(cmp(u,v))continue;
  47.                                                 if(perpendicular(u,v)){
  48.                                                         flag = true;
  49.                                                         break;
  50.                                                 }
  51.                                         }
  52.                                         if(flag)break;
  53.                                 }
  54.                                 if(flag)break;
  55.                         }
  56.                         if(flag)break;
  57.                 }
  58.                 cout<<((flag)?"YES":"NO")<<endl;
  59.         }
  60.         return 0;
  61. }

呼呼~幸好我带了计算几何的模版 = v =

  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter