HDU 6631 line symmetric（计算几何）
发布时间：2020-12-13 22:16:10 所属栏目：PHP教程 来源：网络整理
导读：http://acm.hdu.edu.cn/showproblem.php?pid=6631 题意 给定一个多边形，问是否能在最多移动一个点的情况下使得其变成轴对称图形。 题解 这题我估分2800，800分给几何操作，2000分给细节！ 首先，n=4肯定可以移动使其变成轴对称图形。 n=5我们可以暴力枚举所
|
http://acm.hdu.edu.cn/showproblem.php?pid=6631 题意给定一个多边形，问是否能在最多移动一个点的情况下使得其变成轴对称图形。 题解这题我估分2800，800分给几何操作，2000分给细节！ 首先，n<=4肯定可以移动使其变成轴对称图形。 n>=5我们可以暴力枚举所有对称轴：i和i+1连线的中垂线以及i和i+2连线的中垂线； 时间复杂度n^2，可以接受。
? ? 对称轴将点分成两个部分，如果两边点数相差<=1就满足条件。
如果你觉得这就做完了那你就可以wa哭了。。。 因为有一种情况还没有考虑：移动一个点之后引起图形自交即多边形不合法。 如图：
?
?
? 总结起来就是： 如果有一组E，F不对称， E点或与E直接相连的点跨过了对称轴且F点或与F直接相连的点也跨过了对称轴 那么移动后多边形会自交。 ok，到这里这题的细节就全部分析完毕。 代码很好写： 1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define ll long long 6 #define mk make_pair 7 const int N=2e3+5; 8 const double eps=1e-6; 9 struct Point{ 10 double x,y; 11 Point(double x=0,double y=0):x(x),y(y){}; 12 }; 13 typedef Point Vector; 14 int dcmp(double x){ 15 if(fabs(x)<eps)return 0; 16 return x<0?-1:1; 17 } 18 Vector operator +(Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);} 19 Vector operator -(Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);} 20 Vector operator *(Vector A,double B){return Vector(A.x*B,A.y*B);} 21 Vector operator /(Vector A,double B){return Vector(A.x/B,A.y/B);} 22 bool operator<(const Point&a,const Point&b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} 23 bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;} 24 double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;} 25 double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} 26 Point p[N],a,b,A,B,m,m2,m3,p1,np; 27 int T,n; 28 int judge(int j,int k,Point m,Point m2) { 29 int flag1=0,flag2=0; 30 Vector v1=m2-m; 31 Vector v2=p[j]-m; 32 Vector v3,v4; 33 if(Cross(v1,v2)){ 34 int l=j-1,r=j+1; 35 if(l<1)l+=n; 36 if(r>n)r-=n; 37 v4=p[l]-m; 38 v3=p[r]-m; 39 if(Cross(v1,v4)*Cross(v1,v3)<0)flag1=1; 40 if(Cross(v1,v2)*Cross(v1,v3)<0)flag1=1; 41 } 42 else flag1=1; 43 v2=p[k]-m; 44 if(Cross(v1,v2)){ 45 int l=k+1,r=k-1; 46 if(l<1)l+=n; 47 if(r>n)r-=n; 48 v4=p[l]-m; 49 v3=p[r]-m; 50 if(Cross(v1,v3)<0)flag2=1; 51 if(Cross(v1,v3)<0)flag2=1; 52 } 53 54 else flag2=1; 55 if(flag1&&flag2)return 1; 56 return 0; 57 } 58 int check1(){ 59 for(int i=1;i<=n;i++){ 60 int g=0; 61 A=p[i],B=p[i%n+1]; 62 m.x=(A.x+B.x)/2; 63 m.y=(A.y+B.y)/2; 64 m2.x=m.x+m.y-A.y; 65 m2.y=m.y+A.x-m.x; 66 67 if(n%2){ 68 p1=p[(i+n/2)%n+1]; 69 Vector v1=m2-m; 70 Vector v2=p1-m; 71 if(Cross(v1,v2))g++; 72 } 73 int t=n/2-1; 74 int j=i-1,k=i+2; 75 while(t--){ 76 if(j<1)j+=n; 77 if(k>n)k-=n; 78 m3.x=(p[j].x+p[k].x)/2; 79 m3.y=(p[j].y+p[k].y)/2; 80 Vector AB=B-A; 81 Vector v1=m3-m; 82 Vector v2=p[k]-p[j]; 83 if(Dot(AB,v1)!=0||Dot(v1,v2)!=0){ 84 g++; 85 g+=judge(j,k,m2); 86 } 87 j--; 88 k++; 89 } 90 if(g<=1)return 1; 91 } 92 return 0; 93 } 94 int check2() { 95 for(int i=1;i<=n;i++){ 96 int g=0; 97 A=p[i],B=p[(i+1)%n+1]; 98 m.x=(A.x+B.x)/2; 99 m.y=(A.y+B.y)/2; 100 m2.x=m.x+m.y-A.y; 101 m2.y=m.y+A.x-m.x; 102 p1=p[i%n+1]; 103 Vector v1=m2-m; 104 Vector v2=m2-p1; 105 if(Cross(v1,v2))g++; 106 if(n%2==0){ 107 p1=p[(i+n/2)%n+1]; 108 v1=m2-m; 109 v2=m2-p1; 110 if(Cross(v1,v2))g++; 111 } 112 int j=i-1,k=i+3; 113 114 int t=n/2-1; 115 while(t--){ 116 if(j<1)j+=n; 117 if(k>n)k-=n; 118 m3.x=(p[j].x+p[k].x)/2; 119 m3.y=(p[j].y+p[k].y)/2; 120 Vector AB=B-A; 121 Vector v1=m3-m; 122 Vector v2=p[k]-p[j]; 123 if(Dot(AB,v2)!=0){ 124 g++; 125 g+=judge(j,m2); 126 } 127 j--; 128 k++; 129 } 130 if(g<=1)return 1; 131 } 132 return 0; 133 } 134 int main(){ 135 scanf("%d",&T); 136 while(T--){ 137 scanf("%d",&n); 138 for(int i=0;i<=1000;i++)p[i]=np; 139 for(int i=1;i<=n;i++){ 140 scanf("%lf%lf",&p[i].x,&p[i].y); 141 } 142 if(n<=4){ 143 printf("Yn"); 144 continue; 145 } 146 if(check1())printf("Yn"); 147 else if(check2())printf("Yn"); 148 else printf("Nn"); 149 } 150 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
