首页 > 代码库 > POJ 3293 Rectilinear polygon（几何基础）
POJ 3293 Rectilinear polygon（几何基础）
【题目链接】 http://poj.org/problem?id=3293
【题目大意】
给出一些点，每个点只能向外引出一条平行X轴，和Y轴的边，
问能否构成一个闭多边形，如果能，返回多边形的总边长，否则返回-1
【题解】
我们发现对于每一行或者每一列都必须有偶数个点，且两两之间相邻才能满足条件
所以我们将其连线之后判断是否可以构成一个封闭图形，同时还需要判断这些线是否会相交，
如果相交即不成立
【代码】
#include <cstdio>#include <algorithm>using namespace std;const int N=100010; struct Point{int x,y,id;}p[N];struct Line{ int d,x,y; Line(){} Line(int _d,int _x,int _y):d(_d),x(_x),y(_y){}}l[N];int cmp_x(Point a,Point b){ if(a.x==b.x)return a.y<b.y; return a.x<b.x;}int cmp_y(Point a,Point b){ if(a.y==b.y)return a.x<b.x; return a.y<b.y;}int con[N][2],n,ln,T;int Check(Point a,Point b){ int y=a.y,x1=a.x,x2=b.x; for(int i=0;i<ln;i++){ if(x1<l[i].d&&x2>l[i].d&&l[i].x<y&&l[i].y>y)return 1; }return 0;}int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&p[i].x,&p[i].y); p[i].id=i; }int s=0,cnt=1,flag=0; ln=0; sort(p,p+n,cmp_x); for(int i=1;i<n&&!flag;i++){ if(p[i].x!=p[i-1].x){ if(cnt&1)flag=1; cnt=1; }else{ cnt++; if((cnt&1)==0){ s+=p[i].y-p[i-1].y; con[p[i].id][0]=p[i-1].id; con[p[i-1].id][0]=p[i].id; l[ln++]=Line(p[i].x,p[i-1].y,p[i].y); } } }sort(p,p+n,cmp_y); cnt=1; for(int i=1;i<n&&!flag;i++){ if(p[i].y!=p[i-1].y){ if(cnt&1)flag=1; cnt=1; } else{ cnt++; if((cnt&1)==0){ s+=p[i].x-p[i-1].x; con[p[i].id][1]=p[i-1].id; con[p[i-1].id][1]=p[i].id; if(Check(p[i-1],p[i]))flag=1; } } }int t=1,x=0,c=0; for(;;){ x=con[x][t]; t^=1; c++; if(x==0||flag)break; }if(c!=n)flag=1; if(flag)puts("-1"); else printf("%d\n",s); }return 0;}POJ 3293 Rectilinear polygon（几何基础）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。