problem
- 题意：给出n对多边形，判断每一对多边形是否是由一块矩形一刀切下形成的。
solution
- 一个矩形被切，有4种情况
切到0个顶点，三角形+五边形，或四边形+四边形
切到1个顶点，三角形+四边形
切到2个顶点，三角形+三角形 - 再考虑特殊情况，切线平行坐标轴
那么会得到两个矩形，一条边互相相等
如果不平行（一般情况），那也只有这一条边是不平行的
所以，给出的坐标，最多只有一条不平行，否则就no。 - 对于这一条不平行的情况，因为题目的点是按照顺序给出的，
所以如果相邻两个点的横坐标和纵坐标都不相等，那就是不平行的边
找到这条斜边，如果斜边相等，那么两个图形就可以拼合 - 对于最后一个数据点
在四边形+四边形中，则会产生两个图形唯一的斜边等价、却不能拼成矩形的情况，此时需要特殊判定一下这两个直角梯形的直角腰是否相等。
//超级注释版
#include<bits/stdc++.h>
using namespace std;
//1.分别存储两个图形的斜边(2个点)，顶点数，
vector<int> v[2], n;
//2.特判情况:四边形直角腰，矩形个数
vector<int>len; int flag;
//1.找到斜边
void deal(int id, vector<int>& x, vector<int>& y){
int sz = x.size(); set<int>st;
for(int i = 0; i < sz; i++){
//相邻点横纵坐标都不等：这两点构成斜边。
if(x[i]!=x[(i+1)%sz] && y[i]!=y[(i+1)%sz]){
st.insert(i); st.insert((i+1)%sz);
//如果是四边形：存储直角腰的长度
if(sz==4)len.push_back(abs(x[(i+2)%4]-x[(i+3)%4])+abs(y[(i+2)%4]-y[(i+3)%4]));
}
}
if(st.size()==0){//没有斜边，所以是矩形
//存下两条直角边
v[id].push_back(abs(x[2]-x[0]));
v[id].push_back(abs(y[2]-y[0]));
flag++; //矩形个数+1
}else{
//存储斜边(2个端点)
for(int i : st){
v[id].push_back(x[i]);
v[id].push_back(y[i]);
}
}
}
//2.情况判断
void solve(){
//最多也就三边形+五边形，超过8个点就错。
if(n[0]<=5 && n[1]<=5 && n[0]+n[1]<=8){
if(flag==2){//两个矩形
//只要矩形A(x,y)两条直接边有一条能和矩形B合上就行
int x=v[0][0],y=v[0][1],c=v[1][0],d=v[1][1];
if(x==c||x==d||y==c||y==d){cout<<"YES\n";return;}
}
if(flag==0){//没有矩形
//如果没有斜边，不成立
if(v[0].size()==4 && v[1].size()==4){
//特判直角腰
if(n[0]==4&&n[1]==4&&len[0]!=len[1]){cout<<"NO\n";return;}
//存下两条直角边(斜边分别做垂直的直角三角形)
int x=abs(v[0][2]-v[0][0]),y=abs(v[0][3]-v[0][1]); if(x>y) swap(x,y);
int c=abs(v[1][2]-v[1][0]),d=abs(v[1][3]-v[1][1]); if(c>d) swap(c,d);
//当且仅当直角边都相等，斜边相等
if(x==c&&y==d){cout<<"YES\n";return;}
}
}
//一个矩形的情况不存在
}
cout<<"NO\n";
}
int main(){
int T; cin>>T;
while(T--){
//1. 变量全部初始化
flag = 0; n.clear(); len.clear();
v[0].clear(); v[1].clear();
//2. 输入两个多边形
for(int i = 0; i < 2; i++){
int k; cin>>k; n.push_back(k);
vector<int>x(k), y(k);
for(int j = 0; j < k; j++)cin>>x[j]>>y[j];
//2.1 找到斜边
deal(i,x,y);
}
//3. 结论判断
solve();
}
return 0;
}