首页 > 代码库 > POJ3335 POJ3130 [半平面交]
POJ3335 POJ3130 [半平面交]
终于写出自己的半平面交模板了.......
加入交点的地方用了直线线段相交判定
两个题一样,只不过一个顺时针一个逆时针(给出一个多边形的两种方式啦),反正那个CutPolygon是切掉左面
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>using namespace std;typedef long long ll;const int N=105;const double INF=1e5;const double eps=1e-8;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}inline int sgn(double x){ if(abs(x)<eps) return 0; else return x<0?-1:1;}struct Vector{ double x,y; Vector(double a=0,double b=0):x(a),y(b){} bool operator <(const Vector &a)const{ return sgn(x-a.x)<0||(sgn(x-a.x)==0&&sgn(y-a.y)<0); } void print(char c){printf("%c %lf %lf\n",c,x,y);}};typedef Vector Point;Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}double Len(Vector a){return sqrt(Dot(a,a));}double DisTL(Point p,Point a,Point b){ Vector v1=b-a,v2=p-a; return abs(Cross(v1,v2)/Len(v1));}struct Line{ Point s,t; Line(){} Line(Point a,Point b):s(a),t(b){}};bool isLSI(Line l1,Line l2){ Vector v=l1.t-l1.s,u=l2.s-l1.s,w=l2.t-l1.s; return sgn(Cross(v,u))!=sgn(Cross(v,w));}Point LI(Line a,Line b){ Vector v=a.s-b.s,v1=a.t-a.s,v2=b.t-b.s; double t=Cross(v2,v)/Cross(v1,v2); return a.s+v1*t;}void iniPolygon(Point p[],int &n,double inf){ n=0; p[++n]=Point(-inf,-inf); p[++n]=Point(inf,-inf); p[++n]=Point(inf,inf); p[++n]=Point(-inf,inf);}Point t[N];int tn;void CutPolygon(Point p[],int &n,Point a,Point b){//get the left of a->b memset(t,0,sizeof(t));tn=0; Point c,d,e; for(int i=1;i<=n;i++){ c=p[i],d=p[i%n+1]; if(sgn(Cross(b-a,c-a))>=0) t[++tn]=c; if(isLSI(Line(a,b),Line(c,d))){ e=LI(Line(a,b),Line(c,d));//e.print(‘e‘); t[++tn]=e; } } n=tn;for(int i=1;i<=n;i++)p[i]=t[i];}int n,m;Point p[N],q[N];int main(int argc, const char * argv[]) { while(true){ n=read();if(n==0) break; iniPolygon(q,m,INF); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); for(int i=1;i<=n;i++) CutPolygon(q,m,p[i],p[i%n+1]);//,printf("%d\n",m); if(m) puts("1");else puts("0"); }}
POJ3335 POJ3130 [半平面交]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。