迎着一面矩形的大旗一刀斩下,如果你的刀够快的话,这笔直一刀可以切出两块多边形的残片。反过来说,如果有人拿着两块残片来吹牛,说这是自己迎风一刀斩落的,你能检查一下这是不是真的吗?
注意摆在你面前的两个多边形可不一定是端端正正摆好的,它们可能被平移、被旋转(逆时针90度、180度、或270度),或者被(镜像)翻面。
这里假设原始大旗的四边都与坐标轴是平行的。
输入格式:
输入第一行给出一个正整数N(≤20),随后给出N对多边形。每个多边形按下列格式给出:
k x1 y1 ⋯ xk yk
其中k(2<k≤10)是多边形顶点个数;(xi,yi)(0≤xi,yi≤108)是顶点坐标,按照顺时针或逆时针的顺序给出。
注意:题目保证没有多余顶点。即每个多边形的顶点都是不重复的,任意3个相邻顶点不共线。
输出格式:
对每一对多边形,输出YES或者NO。
输入样例:
8
3 0 0 1 0 1 1
3 0 0 1 1 0 1
3 0 0 1 0 1 1
3 0 0 1 1 0 2
4 0 4 1 4 1 0 0 0
4 4 0 4 1 0 1 0 0
3 0 0 1 1 0 1
4 2 3 1 4 1 7 2 7
5 10 10 10 12 12 12 14 11 14 10
3 28 35 29 35 29 37
3 7 9 8 11 8 9
5 87 26 92 26 92 23 90 22 87 22
5 0 0 2 0 1 1 1 2 0 2
4 0 0 1 1 2 1 2 0
4 0 0 0 1 1 1 2 0
4 0 0 0 1 1 1 2 0
输出样例:
YES
NO
YES
YES
YES
YES
NO
YES
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> PII;PII a[6],b[6];inline void input(PII a[],int &n){scanf("%d",&n);for (int i=0;i<n;i++) {int x,y;scanf("%d%d",&x,&y);a[i]=PII(x,y);}}inline void check(PII a[],int n,int &X,int &x,int &Y,int &y,int &strt){X=x=Y=y=strt=0;for (int i=0;i<n;i++) {if (a[i].first==a[(i+1)%n].first) {strt++;int tmp=abs(a[i].second-a[(i+1)%n].second);if (tmp>Y) y=Y,Y=tmp;else y=tmp;} else if (a[i].second==a[(i+1)%n].second) {strt++;int tmp=abs(a[i].first-a[(i+1)%n].first);if (tmp>X) {x=X,X=tmp;}else {x=tmp;}}}}inline bool penta(int n,int m){int x,X,y,Y,strt;check(b,m,X,x,Y,y,strt);if (strt!=m-1) {return false;}int A=Y-y,B=X-x;check(a,n,X,x,Y,y,strt);if (strt!=n-1) {return false;}return (X==A&&Y==B)||(X==B&&Y==A);}bool quaqua(){int x,X,y,Y,strt;check(b,4,X,x,Y,y,strt);if (strt<3) return false;if (strt==4) {int A=X,B=Y;check(a,4,X,x,Y,y,strt);if (strt!=4) {return false;}return A==X||A==Y||B==X||B==Y;}int height,A,B;if (y==0) {height=Y;A=X;B=x;} else {height=X;A=Y;B=y;}check(a,4,X,x,Y,y,strt);if (strt<3) {return false;}if (y==0) {return height==Y&&x+A==X+B;} else {return height==X&&y+A==Y+B;}}int main(){int T,n,m;scanf("%d",&T);while (T--) {input(a,n);input(b,m);if (n>m) {swap(n,m);swap(a,b);}bool f=false;if (n==4&&m==4) {f=quaqua();}else {f=penta(n,m);}puts(f?"YES":"NO");}return 0;}