pro:给定规则的多边形,规则是指顶点都在整点上,而且是相互垂直的边的交点。 现在给定两个多边形A,B,问A,B缩小,旋转后是否可以变为同一个图形。
sol:缩小的话,直接离散化即可,就可以去掉没用的部分,旋转的话,可以手动旋转4次。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
struct in{
int N,a[maxn],b[maxn],x[maxn],y[maxn];
int lx,ly;
void init()
{
scanf("%d",&N);
rep(i,,N) scanf("%d%d",&a[i],&b[i]);
rep(i,,N) x[i]=a[i],y[i]=b[i];
sort(x+,x+N+); sort(y+,y+N+);
lx=unique(x+,x+N+)-(x+);
rep(i,,N) a[i]=lower_bound(x+,x+lx+,a[i])-x;
ly=unique(y+,y+N+)-(y+);
rep(i,,N) b[i]=lower_bound(y+,y+ly+,b[i])-y;
}
void turn()
{
rep(i,,N){
int t=a[i],q=b[i];
a[i]=q; b[i]=-t+lx+;
}
swap(lx,ly);
}
}A,B;
bool equel()
{
int pos=;
rep(i,,A.N){
if(A.a[i]==B.a[]&&A.b[i]==B.b[]){
pos=i; break;
}
}
if(!pos) return false;
rep(i,pos,A.N)
if(A.a[i]!=B.a[i+-pos]||A.b[i]!=B.b[i+-pos])
return false;
rep(i,,pos-)
if(A.a[i]!=B.a[A.N-pos+i+]||A.b[i]!=B.b[A.N-pos+i+])
return false;
return true;
}
int main()
{
A.init();
B.init();
if(A.N!=B.N) return puts("no"),;
rep(i,,){
if(equel()) return puts("yes"),;
A.turn();
}
puts("no");
return ;
}