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



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/108953189