L3-006 迎风一刀斩 (30 分)-PAT 团体程序设计天梯赛 GPLT

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

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

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

输入格式:

输入第一行给出一个正整数N(≤20),随后给出N对多边形。每个多边形按下列格式给出:

kx1​y1​⋯xkyk

其中k(2<k≤10)是多边形顶点个数;(xi​,yi​)(0≤xi​,yi​≤108)是顶点坐标,按照顺时针或逆时针的顺序给出。

注意:题目保证没有多余顶点。即每个多边形的顶点都是不重复的,任意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

分析:要让两个图形能够拼接成矩形只有四种情况 1.两个直角三角形 2.两个矩形 3.一个三角形配一个五角形 4.两个直角梯形。由于题目特殊的旋转限制,直角边只会和x轴或y轴平行。非矩形情况首先判断是不是有 边数 – 1 的直角边,然后判断两个图形斜边是否相等。四边形则先判断是否是两个直角梯形,是的话高且斜边都相等则符合,如果是两个矩形 任意一边相等即可。k1表示第一个图形的斜率,k2表示第二个图形的斜率,SLength中储存较短的平行于x轴的边,LLength中储存较长的平行于x轴的边,SWidth中储存较短的平行于y轴的边,LWidth中储存较长的平行于y轴的边,res表示有多少条直角边,dif为两点距离~

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版