原题链接
L3-006 迎风一刀斩 （30 分）
迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？
注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。
这里假设原始大旗的四边都与坐标轴是平行的。
输出格式：
对每一对多边形，输出YES或者NO。
输入样例：
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
分析：
除去网上的一些想法，我提供一种我的解题思路。
满足下面的条件即可输出yes。
1.当两个图形的直角数目都等于他们各自图形的点数减去二，同时两个图形非直角的两个角都可以相互拼接成pi(派)或者pi/2(派的一半)，那么如果他们非直角之间的线长度相等，则输出yes。
2.当两个图形的直角数目都等于4，那么只要他们任意一个边互相相等，输出yes。
如果1，2都不满足输出no
一共可以分为5种 都是符合条件1，2的。
#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#define MST(s,q) memset(s,q,sizeof(s))#define INF 0x3f3f3f3f#define MAXN 1005using namespace std;struct node{int x, y;bool z; };long long dis(node a, node b){return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);}long long tmp;long long fun(node A[], int n, int &L, int &W){int cnt = 0;for (int i = 1; i <= n; i++){int pre = i == 1 ? n : i - 1;int next = i == n ? 1 : i + 1;if ((A[i].x == A[pre].x && A[i].y == A[next].y) || (A[i].y == A[pre].y && A[i].x == A[next].x))A[i].z = 1, cnt++;}if (n == 3 && cnt != 1) return -1;if (n == 4 && cnt < 2) return -1;if (n == 4 && cnt == 4) return -2;if (n == 5 && cnt != 3) return -1;int up = -1, down = -1, H = -1;for (int i = 1; i <= n; i++){int pre = i == 1 ? n : i - 1;int next = i == n ? 1 : i + 1;if (A[i].z == 0){if (A[pre].z == 0){tmp = dis(A[i], A[pre]);L = abs(A[i].x - A[pre].x);W = abs(A[i].y - A[pre].y);if (n == 4){if (up == -1) up = (int)sqrt(dis(A[i], A[next]));else down = (int)sqrt(dis(A[i], A[next]));}}else if (A[next].z == 0){tmp = dis(A[i], A[next]);L = abs(A[i].x - A[next].x);W = abs(A[i].y - A[next].y);if (n == 4){if (up == -1) up = (int)sqrt(dis(A[i], A[pre]));else down = (int)sqrt(dis(A[i], A[pre]));}}}else if (A[i].z == 1 && n == 4){if (A[pre].z == 1)H = (int)sqrt(dis(A[i], A[pre]));else H = (int)sqrt(dis(A[i], A[next]));}}if (n == 4)W = abs(up - down), L = H;return tmp;}int main(){int N;cin >> N;int a, b;node A[12], B[12];while (N--){MST(A, 0);MST(B, 0);cin >> a;for (int i = 0; i < a; ++i)cin >> A[i + 1].x >> A[i + 1].y;cin >> b;for (int i = 0; i < b; ++i)cin >> B[i + 1].x >> B[i + 1].y;if (a + b > 8 || a > 5 ){printf("NO\n");continue;}int L1, L2, W1, W2;long long m = fun(A, a, L1, W1), n = fun(B, b, L2, W2);if (m == -1 || n == -1)printf("NO\n");else{if (m == -2 && n == -2){if (dis(A[1], A[2]) == dis(B[1], B[2]) || dis(A[2], A[3]) == dis(B[1], B[2]))printf("YES\n");else printf("NO\n");}else{if (a == 4 && b == 4){if (m == n && (L1 == L2 && W1 == W2))printf("YES\n");else printf("NO\n");continue;}if (m == n && (L1 == L2 || L1 == W2))printf("YES\n");else printf("NO\n");}}}}
