【CCCC】L3-006 迎风一刀斩 (30分)，几何关系，找规律 （拼合多边形==斜边等价）

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;
}