程序设计天梯赛L3-6 迎风一刀斩

题目
可以看这两位大佬的题解研究一下
连接
连接
题意: 有一个各边都平行于坐标轴的矩形(不知道大小)，给定两个k边形，判断能否由这两个k边形组成这个矩形。这两个k边形可能在原始位置的基础上进行了平移、旋转90度、180度、270度，或者镜像翻转。
思路: 找规律。
1.矩形切开有5种情况，不满足这五种情况的寄。
2.满足5种情况的前提下，观察发现，每个k边形需要满足有恰好k-2个直角。另:如果切开成两个矩形要特判，因为各自4个直角。
3.需要满足两个k边形至多有一条边不平行于坐标轴。
4.两个k边形至少保证有一条边相等，不然无法拼接。
5.判断以上4点基本足够，但是有一种特殊情况，当切割成两个直角梯形时要注意判断是否直角腰对应相等。
时间复杂度: O(input)
代码:

#include
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;++i)
int n,m,k,T;
const int N = 1e3+10;
#define int long long
struct node{
	int x,y;
}a[N],b[N];
bool flag;
void check() //检查是否有公共边
{
			set<int> s1;
			set<int> s2;
			for(int i=0;i<n;++i)
			{
				int x1 = a[i].x,y1 = a[i].y;
				int x2 = a[(i+1)%n].x,y2 = a[(i+1)%n].y;
				s1.insert(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));
			}
			for(int i=0;i<m;++i)
			{
				int x1 = b[i].x,y1 = b[i].y;
				int x2 = b[(i+1)%m].x,y2 = b[(i+1)%m].y;
				s2.insert(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));
			}
			bool ok = 0;
			for(auto item:s1)
			{
				if(s2.count(item)) ok = 1;
			}
			flag = ok;
}
void check2()
{
	vector<double> va,vb;
	for(int i=0;i<n;++i)
	{
				int x1 = a[i].x,y1 = a[i].y;
				int x2 = a[(i+1)%n].x,y2 = a[(i+1)%n].y;
				if(!(x1==x2||y1==y2))
				va.push_back(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));
	}
	for(int i=0;i<m;++i)
	{
				int x1 = b[i].x,y1 = b[i].y;
				int x2 = b[(i+1)%m].x,y2 = b[(i+1)%m].y;
				if(!(x1==x2||y1==y2))
				vb.push_back(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));
	}
	if(va.size()==0&&vb.size()==0);
	else if(va.size()==1&&vb.size()==1&&va[0]==vb[0]);
	else flag = 0;
}
void solve()
{
	int cnt1 = 0,cnt2 = 0; //两个多边形的直角数量
	cin>>n; for(int i=0;i<n;++i) cin>>a[i].x>>a[i].y;
	cin>>m; for(int i=0;i<m;++i) cin>>b[i].x>>b[i].y;
	flag = 0;
	if((n==4&&m==4)) flag = 1;
	if((n==3&&m==3)) flag = 1;
	if(((n==4&&m==3)||(n==3&&m==4))) flag = 1;
	if(((n==5&&m==3)||(n==3&&m==5))) flag = 1;
	check2(); //检查是否各有仅一条不平行于坐标轴的边且相等
	if(flag)
	{
		for(int i=0;i<n;++i)
		{
			int l = (i-1+n)%n;
			int r = (i+1)%n;
			int x1 = a[i].x,y1 = a[i].y;
			int x2 = a[l].x,y2 = a[l].y;
			int x3 = a[r].x,y3 = a[r].y;
			if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)) cnt1++;
		}
		for(int i=0;i<m;++i)
		{
			int l = (i-1+m)%m;
			int r = (i+1)%m;
			int x1 = b[i].x,y1 = b[i].y;
			int x2 = b[l].x,y2 = b[l].y;
			int x3 = b[r].x,y3 = b[r].y;
			if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)) cnt2++;
		}
		if(n==4&&m==4)
		{
			if(cnt1==4&&cnt2==4)
			{
				check();
			}
			else if(cnt1==2&&cnt2==2)
			{
					int t1 = 0,t2 = 0;
					vector<node> va,vb;
					for(int i=0;i<n;++i)
				  {
					int l = (i-1+n)%n;
					int r = (i+1)%n;
					int x1 = a[i].x,y1 = a[i].y;
					int x2 = a[l].x,y2 = a[l].y;
					int x3 = a[r].x,y3 = a[r].y;
					if((y1==y2&&x1==x3)||(y1==y3&&x1==x2))
					{
						va.push_back(a[i]);
					}
				  }
				  for(int i=0;i<m;++i)
				  {
					int l = (i-1+m)%m;
					int r = (i+1)%m;
					int x1 = b[i].x,y1 = b[i].y;
					int x2 = b[l].x,y2 = b[l].y;
					int x3 = b[r].x,y3 = b[r].y;
					if((y1==y2&&x1==x3)||(y1==y3&&x1==x2))
					{
						vb.push_back(b[i]);
					}
				  }
				  t1 = abs(va[1].y-va[0].y)+abs(va[1].x-va[0].x);
				  t2 = abs(vb[1].y-vb[0].y)+abs(vb[1].x-vb[0].x);
				  if(t1 != t2) flag = 0;
			}
		}
		else if(cnt1!=n-2||cnt2!=m-2) flag = 0;
	}
	if(flag) puts("YES");
	else puts("NO");
}
signed main(void)
{
	cin>>T;
	while(T--)
	solve();
	return 0;
}