程序设计天梯赛L3-6 迎风一刀斩 (计算几何找规律)

题目 可以看这两位大佬的题解研究一下 连接 连接 题意: 有一个各边都平行于坐标轴的矩形(不知道大小)，给定两个k边形，判断能否由这两个k边形组成这个矩形。这两个k边形可能在原始位置的基础上进行了平移、旋转90度、180度、270度，或者镜像翻转。 思路: 找规律。 1.矩形切开有5种情况，不满足这五种情况的寄。 2.满足5种情况的前提下，观察发现，每个k边形需要满足有恰好k-2个直角。另:如果切开成两个矩形要特判，因为各自4个直角。 3.需要满足两个k边形至多有一条边不平行于坐标轴。 4.两个k边形至少保证有一条边相等，不然无法拼接。 5.判断以上4点基本足够，但是有一种特殊情况，当切割成两个直角梯形时要注意判断是否直角腰对应相等。 时间复杂度: O(input) 代码:

#include
using namespace std;
#define fir(i,a,b) for(int i=a;ia[i].y;
	cin>>m; for(int i=0;i>b[i].x>>b[i].y;
	flag = 0;
	if((n==4&&m==4)) flag = 1;
	if((n==3&&m==3)) flag = 1;
	if(((n==4&&m==3)||(n==3&&m==4))) flag = 1;
	if(((n==5&&m==3)||(n==3&&m==5))) flag = 1;
	check2(); //检查是否各有仅一条不平行于坐标轴的边且相等
	if(flag)
	{
		for(int i=0;i