程序设计天梯赛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;i<=b;++i)
int n,m,k,T;
const int N = 1e3+10;
#define int long long
struct node{int x,y;
}a[N],b[N];
bool flag;
void check() //检查是否有公共边
{set<int> s1;set<int> s2;for(int i=0;i<n;++i){int x1 = a[i].x,y1 = a[i].y;int x2 = a[(i+1)%n].x,y2 = a[(i+1)%n].y;s1.insert(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));}for(int i=0;i<m;++i){int x1 = b[i].x,y1 = b[i].y;int x2 = b[(i+1)%m].x,y2 = b[(i+1)%m].y;s2.insert(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));}bool ok = 0;for(auto item:s1){if(s2.count(item)) ok = 1;}flag = ok;
}
void check2()
{vector<double> va,vb;for(int i=0;i<n;++i){int x1 = a[i].x,y1 = a[i].y;int x2 = a[(i+1)%n].x,y2 = a[(i+1)%n].y;if(!(x1==x2||y1==y2))va.push_back(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));}for(int i=0;i<m;++i){int x1 = b[i].x,y1 = b[i].y;int x2 = b[(i+1)%m].x,y2 = b[(i+1)%m].y;if(!(x1==x2||y1==y2))vb.push_back(sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1)));}if(va.size()==0&&vb.size()==0);else if(va.size()==1&&vb.size()==1&&va[0]==vb[0]);else flag = 0;
}
void solve()
{int cnt1 = 0,cnt2 = 0; //两个多边形的直角数量cin>>n; for(int i=0;i<n;++i) cin>>a[i].x>>a[i].y;cin>>m; for(int i=0;i<m;++i) cin>>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<n;++i){int l = (i-1+n)%n;int r = (i+1)%n;int x1 = a[i].x,y1 = a[i].y;int x2 = a[l].x,y2 = a[l].y;int x3 = a[r].x,y3 = a[r].y;if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)) cnt1++;}for(int i=0;i<m;++i){int l = (i-1+m)%m;int r = (i+1)%m;int x1 = b[i].x,y1 = b[i].y;int x2 = b[l].x,y2 = b[l].y;int x3 = b[r].x,y3 = b[r].y;if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)) cnt2++;}if(n==4&&m==4){if(cnt1==4&&cnt2==4){check();}else if(cnt1==2&&cnt2==2){int t1 = 0,t2 = 0;vector<node> va,vb;for(int i=0;i<n;++i){int l = (i-1+n)%n;int r = (i+1)%n;int x1 = a[i].x,y1 = a[i].y;int x2 = a[l].x,y2 = a[l].y;int x3 = a[r].x,y3 = a[r].y;if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)){va.push_back(a[i]);}}for(int i=0;i<m;++i){int l = (i-1+m)%m;int r = (i+1)%m;int x1 = b[i].x,y1 = b[i].y;int x2 = b[l].x,y2 = b[l].y;int x3 = b[r].x,y3 = b[r].y;if((y1==y2&&x1==x3)||(y1==y3&&x1==x2)){vb.push_back(b[i]);}}t1 = abs(va[1].y-va[0].y)+abs(va[1].x-va[0].x);t2 = abs(vb[1].y-vb[0].y)+abs(vb[1].x-vb[0].x);if(t1 != t2) flag = 0;}}else if(cnt1!=n-2||cnt2!=m-2) flag = 0;}if(flag) puts("YES");else puts("NO");
}
signed main(void)
{cin>>T;while(T--)solve();return 0;
}

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