L3-006 迎风一刀斩

题目链接

借鉴了其他同志的思路
很复杂的一道模拟题！！！

---

关键点：
1、如图，由于题目明确了，初始旗帜为矩形，因此一共有这5种裁剪法。
2、题解主要注重以下方面：

1. 斜线（裁剪线）的位置是否符合
2. 两条线求和能不能
3. 是否有直角，有多少个直角

3、给出的点是顺时针或逆时针，按顺序求边长即可，勿要两两相求
4、按点的数量分别判断是否符合

---

• 对于1号图形，它们各个边长相同即可
• 对于2号和5号，由于N都为4，因此放一起判断。2号：拥有4个直角，裁开的两部分中，任意一个直角的两条直角边中，有一个边相同；5号：斜边相等，斜边顺时针（或逆时针）2个位置的边相同（就是斜边对面的那条边）。两部分的斜边的两侧的边，两两相加相等
• 对于3号，斜边相等，5个顶点的部分记为L，3个顶点部分记为R，L的两个较小边和R的直角边对应相加（如何对应相加？枚举出所有情况，最多也就4种），等于L的两条最大边。
• 对于4号，斜边相同，两部分有一条边相同，剩下的和上述一样，对应相加看是否相等。

---

L3-006 迎风一刀斩
分数 30
作者 刘汝佳
单位 北京尔宜居科技有限责任公司
迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。

这里假设原始大旗的四边都与坐标轴是平行的。

输入样例：
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
#include
#include
#include
#include
using namespace std;
#define lens(x1,y1,x2,y2)(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)))
vector<int> the_edge(vector<pair<int, int>> v) {//求边长
	int right;
	vector<int> res;
	for (int i = 0; i < v.size(); i++) {
		if (i == v.size() - 1)	right = 0;
		else right = i + 1;
		int temp = lens(v[i].first, v[i].second, v[right].first, v[right].second);
		res.push_back(temp);
	}
	return res;
}
vector<bool> the_angel(vector<pair<int, int>> v) {//这个点是否为直角
	vector<bool> res;
	int left, right;
	for (int i = 0; i < v.size(); i++) {
		left = i == 0 ? v.size() - 1 : i - 1;
		right = i == v.size() - 1 ? 0 : i + 1;
		if ((v[i].first == v[left].first && v[i].second == v[right].second) || (v[i].first == v[right].first && v[i].second == v[left].second))
			res.push_back(true);
		else res.push_back(false);
	}
	return res;
}
int the_line(vector<bool> v) {//求斜线位置，-2表示图形2这种情况，-1表示不合条件
	int left, cnt = 0,ans=-2;
	for (int i = 0; i < v.size(); i++) {
		left = i == 0 ? v.size() - 1 : i - 1;
		if (v[i])	cnt++;
		else if (v[left])	ans = i;
	}
	return cnt >= (v.size() - 2) ? ans : -1;
}
int main() {
	ios::sync_with_stdio(false);
	int N,n1,n2;
	cin >> N;
	while (N--) {
		cin >> n1;
		vector<pair<int, int>> v1(n1);
		for (int i = 0; i < n1; i++)	cin >> v1[i].first >> v1[i].second;
		cin >> n2;
		vector<pair<int, int>> v2(n2);
		for (int i = 0; i < n2; i++)cin >> v2[i].first >> v2[i].second;
		if (n1 > n2) {
			swap(n1, n2);
			swap(v1, v2);
		}
		vector<int> e1 = the_edge(v1),	e2 = the_edge(v2);
		vector<bool> a1 = the_angel(v1),	a2 = the_angel(v2);
		int l1 = the_line(a1),	l2 = the_line(a2);
		//cout << "l1:" << l1 << " l2:" << l2 << endl;
		bool flag = false;
		if (l1 == -1 || l2 == -1);
		else if (n1 == 3&&n2== 3) {
			sort(e1.begin(), e1.end());	sort(e2.begin(), e2.end());
			flag = (e1 == e2);
		}
		else if (n1 == 4&& n2== 4) {
			if (l1 == -2 && l2 == -2 && (e1[0] == e2[0] || e1[0] == e2[1] || e1[1] == e2[0] || e1[1] == e2[1]))
				flag = true;
			else {
				bool f1 = (e1[(l1 + 1) % 4] + e2[(l2 + 1) % 4] == e1[(l1 + 3) % 4] + e2[(l2 + 3) % 4]);
				bool f2 = (e1[(l1 + 1) % 4] + e2[(l2 + 3) % 4] == e1[(l1 + 3) % 4] + e2[(l2 + 1) % 4]);
				if (e1[l1] == e2[l2] && e1[(l1 + 2) % 4] == e2[(l2 + 2) % 4] && (f1 || f2))
					flag = true;
			}
		}
		else if (n1 == 3 && n2 == 5) {
			vector<int> temp = e2;
			bool f1 = false, f2 = false;
			int len1, len2;
			sort(temp.begin(), temp.end());
			len1 = e1[(l1 + 1) % 3] + e2[(l2 + 1) % 5];
			len2 = e1[(l1 + 2) % 3] + e2[(l2 + 4) % 5];
			if ((len1 == temp[3] && len2 == temp[4]) || (len1 == temp[4] && len2 == temp[3]))	f1 = true;
			len1 = e1[(l1 + 1) % 3] + e2[(l2 + 4) % 5];
			len2 = e1[(l1 + 2) % 3] + e2[(l2 + 1) % 5];
			if ((len1 == temp[3] && len2 == temp[4]) || (len1 == temp[4] && len2 == temp[3]))	f2 = true;
			if (e1[l1] == e2[l2] && (f1 || f2))	flag = true;
		}
		else if (n1 == 3 && n2 == 4) {
			bool f0 = (e1[(l1 + 1) % 3] == e2[(l2 + 2) % 4] || e1[(l1 + 2) % 3] == e2[(l2 + 2) % 4]);
			bool f1 = (e1[(l1 + 1) % 3] + e2[(l2 + 1) % 4] == e2[(l2 + 3) % 4]);
			bool f2 = (e1[(l1 + 2) % 3] + e2[(l2 + 1) % 4] == e2[(l2 + 3) % 4]);
			bool f3 = (e1[(l1 + 1) % 3] + e2[(l2 + 3) % 4] == e2[(l2 + 1) % 4]);
			bool f4 = (e1[(l1 + 2) % 3] + e2[(l2 + 3) % 4] == e2[(l2 + 1) % 4]);
			if(e1[l1]==e2[l2]&&f0&&(f1||f2||f3||f4)	)
				flag=true;
		}
		string ans = flag ? "YES" : "NO";
		cout << ans << endl;
	}
	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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102