hdu 6631 线对称

by ·0评论

2019杭电多校第五场08

平面上给定一个简单多边形，问最多移动一个点能否使这个多边形对称。要求最终图形是简单多边形。

细节需要注意。一个是简单多边形判断的时候所有点需要在对称轴同一侧。一个是可能的对称轴不只有原多边形相对的两个点或边，或者说对称轴可能被移动。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef double db;
  5. const db PI=acos(-1);
  6. const db eps=1e-8, inf=1e12;
  7.  
  8. bool eq(db x){return fabs(x)<eps;}
  9. int sgn(db x){
  10.     if (x<=-eps) return -1;
  11.     return x>=eps;
  12. }
  13.  
  14. #define Vec const vec &
  15. #define Point const point &
  16. struct vec{
  17.     db x,y;
  18.     vec():x(0),y(0){}
  19.     vec(db x, db y):x(x),y(y){} //[i] init-list is easier to use in c++1x
  20.     vec(db theta):x(cos(theta)),y(sin(theta)){}
  21.  
  22.     bool operator==(Vec v) const{return eq(x-v.x) && eq(y-v.y);}
  23.     db ang() const{return atan2(y,x);}
  24.  
  25.     vec operator+(Vec v) const{return vec(x+v.x,y+v.y);}
  26.     vec operator-(Vec v) const{return vec(x-v.x,y-v.y);}
  27.     vec operator*(db a) const{return vec(x*a,y*a);}
  28.     vec operator/(db a) const{return vec(x/a,y/a);}
  29.  
  30.     db operator|(Vec v) const{return x*v.x+y*v.y;} //dot
  31.     db operator&(Vec v) const{return x*v.y-y*v.x;} //cross
  32.     db operator!() const{return sqrt(x*x+y*y);}    //len
  33.  
  34.     bool operator<(Vec v) const{return x==v.x?y<v.y:x<v.x;}
  35.     vec std() const{return *this/!*this;}
  36.     vec rot(db rad) const{return vec(x*cos(rad)-y*sin(rad), x*sin(rad)+y*cos(rad));}
  37.     vec l90() const{return vec(-y,x);}
  38.     vec r90() const{return vec(y,-x);}
  39.     vec vert() const{return (*this).l90().std();}  //l90 and standard
  40.  
  41.     void rd(){scanf("%lf%lf",&x,&y);}
  42.     void prt(){printf("%f %f\n",x,y);}
  43.     friend ostream& operator<<(ostream &o, Vec v){return o<<v.x<<','<<v.y;}
  44. }p[2010];
  45. typedef vec point;
  46.  
  47. //point projection on line A+tV
  48. point lineProj(Point p, Point s, Vec v){
  49.     return s+v*(v|p-s)/(v|v);
  50. }
  51. //symmetric point of P about line A+tV
  52. point symmetric(Point p, Point s, Vec v){
  53.     return lineProj(p,s,v)*2-p;
  54. }
  55.  
  56. db cross(Point a, Point b, Point c){return b-a & c-a;}
  57. bool onLine(Point p, Point a, Point b){return eq(p-a&b-a);}
  58.  
  59. int main(){
  60.     int T; cin>>T;
  61.     while (T--){
  62.         int n; cin>>n;
  63.         for (int i=0;i<n;i++) p[i].rd();
  64.         if (n==3){
  65.             puts("Y");
  66.             continue;
  67.         }
  68.         db area=0;
  69.         for (int i=2;i<n;i++){
  70.             area+=cross(p[0],p[i-1],p[i]);
  71.         }
  72.         if (area<0) reverse(p,p+n);
  73.         for (int i=0;i<n;i++) p[i+n]=p[i];
  74.         if (n&1){
  75.             int i;
  76.             for (i=0;i<n;i++){
  77.                 int des=i+n/2;
  78.                 point p1=(p[des]+p[des+1])/2;
  79.                 point v1=p1-p[i];
  80.                 int cnt=0,j;
  81.  
  82.                 for (j=1;j<=n/2;j++){
  83.                     if (cross(p[i],p1,p[i+j])>-eps && cross(p[i],p1,p[(i-j+n)%n]<eps)) break;
  84.                     if (!(symmetric(p[i+j],p[i],v1)==p[(i-j+n)%n]))
  85.                         cnt++;
  86.                     if (cnt>1) break;
  87.                 }
  88.                 if (j==n/2+1){
  89.                     puts("Y");
  90.                     break;
  91.                 }
  92.                 p1=(p[(i-1+n)%n]+p[i+1])/2;
  93.                 v1=(p[i+1]-p1).vert();
  94.                 cnt=1;
  95.                 if (!onLine(p[i],p1,p1+v1)){
  96.                     for (j=2;j<=n/2;j++){
  97.                         if (cross(p[i],p1,p[i+j])>-eps && cross(p[i],p1,p[(i-j+n)%n]<eps)) break;
  98.                         if (!(symmetric(p[i+j],p1,v1)==p[(i-j+n)%n]))
  99.                             cnt++;
  100.                         if (cnt>1) break;
  101.                     }
  102.                     if (j==n/2+1){
  103.                         puts("Y");
  104.                         break;
  105.                     }
  106.                 }
  107.             }
  108.             if (i==n) puts("N");
  109.         }
  110.         else{
  111.             int i;
  112.             for (i=0;i<n/2;i++){
  113.                 int des=i+n/2;
  114.                 point v1=p[des]-p[i];
  115.                 int cnt=0,j;
  116.                 for (j=1;j<n/2;j++){
  117.                     if (cross(p[i],p[des],p[i+j])>-eps && cross(p[i],p[des],p[(i-j+n)%n])<eps) break;
  118.                     if (!(symmetric(p[i+j],p[i],v1)==p[(i-j+n)%n]))
  119.                         cnt++;
  120.                     if (cnt>1) break;
  121.                 }
  122.                 if (j==n/2){
  123.                     puts("Y");
  124.                     break;
  125.                 }
  126.                 vec p1=(p[(i-1+n)%n]+p[i+1])/2;
  127.                 v1=(p[i+1]-p1).vert();
  128.                 cnt=1;
  129.                 if (onLine(p[i],p1,p1+v1) || onLine(p[des],p1,p1+v1)){
  130.                     for (j=2;j<n/2;j++){
  131.                         if (cross(p[i],p1,p[i+j])>-eps && cross(p[i],p1,p[(i-j+n)%n]<eps)) break;
  132.                         if (!(symmetric(p[i+j],p1,v1)==p[(i-j+n)%n]))
  133.                             cnt++;
  134.                         if (cnt>1) break;
  135.                     }
  136.                     if (j==n/2){
  137.                         puts("Y");
  138.                         break;
  139.                     }
  140.                 }
  141.             }
  142.             if (i==n/2){
  143.                 for (i=0;i<n/2;i++){
  144.                     int des=i+n/2;
  145.                     point p0=(p[i+1]+p[i])/2;
  146.                     vec v1=(p[i+des+1]+p[i+des])/2;
  147.                     int cnt=0,j;
  148.                     for (j=0;j<n/2;j++){
  149.                         if (cross(p0,p0+v1,p[i+1+j])>-eps && cross(p0,p0+v1,p[(i-j+n)%n])<eps) break;
  150.                         if (!(symmetric(p[i+1+j],p0,v1)==p[(i-j+n)%n]))
  151.                             cnt++;
  152.                         if (cnt>1) break;
  153.                     }
  154.                     if (j==n/2){
  155.                         puts("Y");
  156.                         break;
  157.                     }
  158.                     v1=(p[i+1]-p[i]).vert();
  159.                     cnt=0;
  160.                     for (j=1;j<n/2;j++){
  161.                         if (cross(p0,p0+v1,p[i+1+j])>-eps && cross(p0,p0+v1,p[(i-j+n)%n])<eps) break;
  162.                         if (!(symmetric(p[i+1+j],p0,v1)==p[(i-j+n)%n]))
  163.                             cnt++;
  164.                         if (cnt>1) break;
  165.                     }
  166.                     if (j==n/2){
  167.                         puts("Y");
  168.                         break;
  169.                     }
  170.                 }
  171.                 if (i==n/2) puts("N");
  172.             }
  173.  
  174.         }
  175.     }
  176.     return 0;
  177. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注