L3-006. 迎风一刀斩

迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

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

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

输入格式：

输入第一行给出一个正整数N（<=20），随后给出N对多边形。每个多边形按下列格式给出：

k x₁ y₁ ... x_k y_k

其中k（2 < k <= 10）是多边形顶点个数；(x_i, y_i)（0 <= x_i, y_i <= 10⁸）是顶点坐标，按照顺时针或逆时针的顺序给出。

注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意3个相邻顶点不共线。

输出格式：

对每一对多边形，输出"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


一共四种情况可以组合成矩形，一种是两个全等直角三角形，一种是两个四边形如果是梯形则斜边相同，如果是矩形则有一条边相同即可，在一种是一个直角梯形加一个直角三角形，斜边要相同，最后是一个五边形加一个直角三角形。
代码：

#include 
#include 
#include 
using namespace std;
int xx1[11],yy1[11],xx2[11],yy2[11];
int n,k1,k2;
int len_(int a,int b,int c,int d)
{if(a == c)return abs(b - d);return abs(a - c);
}
int check_p(int x,int y)
{if(x > 5 || y < 3)return 0;int a = -1,b = -1,c1,d1,c2,d2;for(int i = 0;i < y;i ++){if(xx2[i] != xx2[(i + 1) % y] && yy2[i] != yy2[(i + 1) % y]){if(b == -1)b = i,c2 = abs(xx2[i] - xx2[(i + 1) % y]),d2 = abs(yy2[i] - yy2[(i + 1) % y]);else return 0;}else if(xx2[i] == xx2[(i + 1) % y] && yy2[i] == yy2[(i + 1) % y])return 0;}for(int i = 0;i < x;i ++){if(xx1[i] != xx1[(i + 1) % x] && yy1[i] != yy1[(i + 1) % x]){if(a == -1)a = i,c1 = abs(xx1[i] - xx1[(i + 1) % x]),d1 = abs(yy1[i] - yy1[(i + 1) % x]);else return 0;}else if(xx1[i] == xx1[(i + 1) % x] && yy1[i] == yy1[(i + 1) % x])return 0;}if(a == -1 && b != -1 || a != -1 && b == -1)return 0;if(x == 4 && y == 4){if(a == -1 && b == -1){int e1 = len_(xx1[0],yy1[0],xx1[1],yy1[1]);int e2 = len_(xx1[1],yy1[1],xx1[2],yy1[2]);int e3 = len_(xx2[0],yy2[0],xx2[1],yy2[1]);int e4 = len_(xx2[1],yy2[1],xx2[2],yy2[2]);if(e1 == e3 || e2 == e4 || e1 == e4 || e2 == e3)return 1;///有一对边相等就可以接合return 0;}int e1 = len_(xx1[a],yy1[a],xx1[(a - 1 + x) % x],yy1[(a - 1 + x) % x]);int e2 = len_(xx1[(a + 1) % x],yy1[(a + 1) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);int e3 = len_(xx2[b],yy2[b],xx2[(b - 1 + y) % y],yy2[(b - 1 + y) % y]);int e4 = len_(xx2[(b + 1) % y],yy2[(b + 1) % y],xx2[(b + 2) % y],yy2[(b + 2) % y]);int e5 = len_(xx1[(a + 3) % x],yy1[(a + 3) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);int e6 = len_(xx2[(b + 3) % y],yy2[(b + 3) % y],xx2[(b + 2) % y],yy2[(b + 2) % y]);if(e5 != e6)return 0;if(!(c1 == e5 && d1 == abs(e2 - e1) || d1 == e5 && c1 == abs(e2 - e1)))return 0;if(!(c2 == e6 && d2 == abs(e3 - e4) || d2 == e6 && c2 == abs(e3 - e4)))return 0;if(abs(e2 - e1) == abs(e3 - e4))return 1;return 0;}else if(x == 3 && y == 3){if(a == -1 && b == -1)return 0;int e1 = len_(xx1[a],yy1[a],xx1[(a - 1 + x) % x],yy1[(a - 1 + x) % x]);int e2 = len_(xx1[(a + 1) % x],yy1[(a + 1) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);int e3 = len_(xx2[b],yy2[b],xx2[(b - 1 + y) % y],yy2[(b - 1 + y) % y]);int e4 = len_(xx2[(b + 1) % y],yy2[(b + 1) % y],xx2[(b + 2) % y],yy2[(b + 2) % y]);if(e1 == e3 && e2 == e4 || e1 == e4 && e2 == e3)return 1;///
        return 0;}else if(x == 4 && y == 3){if(a == -1 && b == -1)return 0;int e1,e2,e3,e4,e5;e1 = len_(xx2[b],yy2[b],xx2[(b - 1 + y) % y],yy2[(b - 1 + y) % y]);e2 = len_(xx2[(b + 1) % y],yy2[(b + 1) % y],xx2[(b + 2) % y],yy2[(b + 2) % y]);e3 = len_(xx1[a],yy1[a],xx1[(a - 1 + x) % x],yy1[(a - 1 + x) % x]);e4 = len_(xx1[(a + 1) % x],yy1[(a + 1) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);e5 = len_(xx1[(a + 3) % x],yy1[(a + 3) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);e3 = abs(e3 - e4);if(!(c1 == e5 && d1 == e3 || c1 == e3 && d1 == e5))return 0;if(e5 == e1 && e2 == e3 || e5 == e2 && e1 == e3)return 1;return 0;}else if(x == 5 && y == 3){if(a == -1 && b == -1)return 0;int e1 = len_(xx1[a],yy1[a],xx1[(a - 1 + x) % x],yy1[(a - 1 + x) % x]);int e2 = len_(xx1[(a + 1) % x],yy1[(a + 1) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);int e3 = len_(xx2[b],yy2[b],xx2[(b - 1 + y) % y],yy2[(b - 1 + y) % y]);int e4 = len_(xx2[(b + 1) % y],yy2[(b + 1) % y],xx2[(b + 2) % y],yy2[(b + 2) % y]);int e5 = len_(xx1[(a - 1 + x) % x],yy1[(a - 1 + x) % x],xx1[(a - 2 + x) % x],yy1[(a - 2 + x) % x]);int e6 = len_(xx1[(a + 3) % x],yy1[(a + 3) % x],xx1[(a + 2) % x],yy1[(a + 2) % x]);e1 = abs(e1 - e6);e2 = abs(e2 - e5);if(!(c1 == e1 && d1 == e2 || c1 == e2 && d1 == e1))return 0;if(e1 == e3 && e2 == e4 || e1 == e4 && e2 == e3)return 1;return 0;}return 0;
}int main()
{cin>>n;for(int i = 0;i < n;i ++){cin>>k1;for(int j = 0;j < k1;j ++){cin>>xx1[j]>>yy1[j];}cin>>k2;for(int j = 0;j < k2;j ++){cin>>xx2[j]>>yy2[j];}if(k1 < k2)swap(k1,k2),swap(xx1,xx2),swap(yy1,yy2);if(!check_p(k1,k2))cout<<"NO";else cout<<"YES";cout<<endl;}
}

转载于:https://www.cnblogs.com/8023spz/p/8640772.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！