首页 > 代码库 > POJ 3449 Geometric Shapes 判断多边形相交
POJ 3449 Geometric Shapes 判断多边形相交
题意不难理解，给出多个多边形，输出多边形间的相交情况（嵌套不算相交），思路也很容易想到。枚举每一个图形再枚举每一条边
恶心在输入输出，不过还好有sscanf()，不懂可以查看cplusplus网站
根据正方形对角的两顶点求另外两个顶点公式：
x2 = (x1+x3-y3+y1)/2; y2 = (x3-x1+y1+y3)/2;
x4= (x1+x3+y3-y1)/2; y4 = (-x3+x1+y1+y3)/2;
还有很多细节要处理
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <map>using namespace std;const double eps = 1e-8;const double PI = acos(-1.0);int sgn(double x){ if(fabs(x) < eps) return 0; return x < 0 ? -1:1;}struct Point{ double x,y; Point() {} Point(double _x,double _y) { x = _x,y = _y; } Point operator -(const Point &b)const { return Point(x - b.x,y - b.y); } //叉积 double operator ^(const Point &b)const { return x*b.y - y*b.x; } //点积 double operator *(const Point &b)const { return x*b.x + y*b.y; }};struct Line{ Point p,q; Line() {}; Line(Point _p,Point _q) { p = _p,q = _q; }};//*判断线段相交bool inter(Line l1,Line l2){ return max(l1.p.x,l1.q.x) >= min(l2.p.x,l2.q.x) && max(l2.p.x,l2.q.x) >= min(l1.p.x,l1.q.x) && max(l1.p.y,l1.q.y) >= min(l2.p.y,l2.q.y) && max(l2.p.y,l2.q.y) >= min(l1.p.y,l1.q.y) && sgn((l2.p-l1.q)^(l1.p-l1.q))*sgn((l2.q-l1.q)^(l1.p-l1.q)) <= 0 && sgn((l1.p-l2.q)^(l2.p-l2.q))*sgn((l1.q-l2.q)^(l2.p-l2.q)) <= 0;}const int maxn=30;struct Shape{ char id; int nump; Point p[maxn];} shp[maxn];bool cmp(Shape a,Shape b){ return a.id<b.id;}char str[20];int num[maxn];char inters[maxn][maxn];map<string,int>mp;int main(){// freopen("in.txt","r",stdin); mp["square"]=2; mp["line"]=2; mp["triangle"]=3; mp["rectangle"]=3; int cnt=0; while(scanf("%s",str)) { if(strcmp(str,".")==0) break; if(strcmp(str,"-")!=0) { shp[cnt].id=str[0]; char str_sh[20]; scanf("%s",str_sh); int n; if(mp.count(str_sh)) n=mp[str_sh]; else scanf("%d",&n); shp[cnt].nump=0; for(int i=0; i<n; i++) { scanf("%s",str); int x,y; sscanf(str,"%*c%d%*c%d",&x,&y); shp[cnt].p[shp[cnt].nump++]=Point(x,y); } if(strcmp(str_sh,"rectangle")==0) { Point p1=shp[cnt].p[0]; Point p2=shp[cnt].p[1]; Point p3=shp[cnt].p[2]; shp[cnt].p[shp[cnt].nump++]=Point(p1.x+p3.x-p2.x,p1.y+p3.y-p2.y); } if(strcmp(str_sh,"square")==0) { Point p1=shp[cnt].p[0]; Point p3=shp[cnt].p[1]; shp[cnt].p[shp[cnt].nump++]=Point((p1.x+p3.x-p3.y+p1.y)/2,(p3.x-p1.x+p1.y+p3.y)/2); shp[cnt].p[shp[cnt].nump++]=Point((p1.x+p3.x+p3.y-p1.y)/2,(-p3.x+p1.x+p1.y+p3.y)/2); swap(shp[cnt].p[1],shp[cnt].p[2]); } cnt++; continue; } sort(shp,shp+cnt,cmp); memset(num,0,sizeof(num)); for(int i=0; i<cnt; i++) { for(int j=i+1; j<cnt; j++) { bool flag=false; int num1=shp[i].nump; int num2=shp[j].nump; for(int k1=0; k1<num1 && !flag; k1++) { for(int k2=0; k2<num2 && !flag; k2++) { if(inter(Line(shp[i].p[k1],shp[i].p[(k1+1)%num1]),Line(shp[j].p[k2],shp[j].p[(k2+1)%num2]))) { inters[i][num[i]++]=shp[j].id; inters[j][num[j]++]=shp[i].id; flag=true; } } } } } for(int i=0; i<cnt; i++) { printf("%c ",shp[i].id); if(num[i]==0) printf("has no intersections\n"); else if(num[i]==1) printf("intersects with %c\n",inters[i][0]); else if(num[i]==2) printf("intersects with %c and %c\n",inters[i][0],inters[i][1]); else { printf("intersects with "); for(int j=0;j<num[i]-1;j++) printf("%c, ",inters[i][j]); printf("and %c\n",inters[i][num[i]-1]); } } cnt=0; puts(""); } return 0;}
POJ 3449 Geometric Shapes 判断多边形相交
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。