首页 > 代码库 > poj1859The Perfect Symmetry

poj1859The Perfect Symmetry

链接

按x或y排序,假如有对称点的话,头尾相对。

 1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 10000012 #define LL long long13 #define INF 0xfffffff14 const double eps = 1e-8;15 const double pi = acos(-1.0);16 const double inf = ~0u>>2;17 struct Point18 {19     double x,y;20     Point(double x=0,double y=0):x(x),y(y) {}21 }p[N];22 typedef Point pointt;23 pointt operator + (Point a,Point b)24 {25     return Point(a.x+b.x,a.y+b.y);26 }27 pointt operator - (Point a,Point b)28 {29     return Point(a.x-b.x,a.y-b.y);30 }31 int dcmp(double x)32 {33     if(fabs(x)<eps) return 0;34     else return x<0?-1:1;35 }36 bool cmp(Point a,Point b)37 {38     if(dcmp(a.x-b.x)==0)39     return a.y<b.y;40     return a.x<b.x;41 }42 int main()43 {44     int n,i,j;45     while(scanf("%d",&n)&&n)46     {47         for(i = 1; i <= n ;i++)48         scanf("%lf%lf",&p[i].x,&p[i].y);49         sort(p+1,p+n+1,cmp);50         double tx = (p[1].x+p[n].x)/2,ty = (p[1].y+p[n].y)/2;51         int flag =1 ;52         for(i = 2 ; i <= n; i++)53         {54             double x = (p[i].x+p[n-i+1].x)/2;55             double y = (p[i].y+p[n-i+1].y)/2;56             if(dcmp(x-tx)!=0||dcmp(y-ty)!=0)57             {58                 flag = 0;59                 break;60             }61         }62         if(flag)63         printf("V.I.P. should stay at (%.1f,%.1f).\n",tx,ty);64         else65         printf("This is a dangerous situation!\n");66     }67     return 0;68 }
View Code