Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
雁过留声——攻下第一个半平面交计算几何,细心大胆。 使用O(nlogn)的斜率排序+增量即可AC。 鸣谢 http://hi.baidu.com/tclsm2008/blog/item/3616201a852cc5118618bfef.html 如果不知道半平面交怎么写,可以当上面那个网址去模仿一下。 我的代码几乎是从那里翻译来的。 struct point{double x,y;}; struct line{point a,b;}; double Abs(double a){return a<0.0?-a:a;} double operator*(point x,point y){ return x.x*y.y-x.y*y.x; } point operator-(point x,point y){ x.x-=y.x;x.y-=y.y; return x; } point operator*(line x,line y){ /*x.a y.a \/ /\ y.b x.b */ double a1=(y.b-x.a)*(y.a-x.a), a2=(y.a-x.b)*(y.b-x.b); point r; r.x=(x.a.x*a2+x.b.x*a1)/(a2+a1); r.y=(x.a.y*a2+x.b.y*a1)/(a2+a1); return r; } int operator==(point x,point y){ return Abs(x.x-y.x)<zero && Abs(x.y-y.y)<zero; } int N; line L[NMax]; double arc[NMax]; int bigger(double a,double b){ return a-b>zero; } void exchange(int i,int j){ double t;line tt; tt=L[i];L[i]=L[j];L[j]=tt; t=arc[i];arc[i]=arc[j];arc[j]=t; } void qs(int b,int e){int j; if (b>=e)return; exchange(b,(b+e)>>1); for (int i=j=b+1;i<=e;i++)if (bigger(arc[b],arc[i])) exchange(i,j++); exchange(--j,b); qs(b,j-1);qs(j+1,e); } int queue[NMax]; point pt[NMax+1]; int onLeft(point a,point b,point c){ //(-1,0) is on left (0,1) return (b-a)*(c-a)<zero; } double Half_Plane_Cross(){ int top,bot; top=0;bot=0; line l;l.a.x=0;l.a.y=MaxL;l.b.x=0;l.b.y=0; pt[0]=L[0].a;pt[0].x=-100000000; queue[0]=0; for (int i=1;i<N+1;i++)pt[i].x=-MaxL-MaxL; for (int i=1;i<N;i++){ if (pt[bot+1]==pt[top] && onLeft(L[i].a,pt[top],L[i].b)) continue; while (top<=bot && !onLeft(L[i].a,pt[bot],L[i].b))bot--; if (top>bot)return 0.0; pt[bot+1]=L[queue[bot]]*L[i]; bot++;queue[bot]=i; if (bigger(L[i].a.y,L[i].b.y)){ while (top<=bot && !onLeft(L[i].a,pt[top+1],L[i].b))top++; if (top>bot)return 0.0; pt[top]=L[queue[top]]*L[i]; pt[bot+1]=pt[top]; } } double ret; ret=0.0; for (int i=top;i<=bot;i++) ret+=pt[i]*pt[i+1]; return Abs(ret)*0.5; } int main() { scanf("%d",&N); for (int i=0;i<N;i++) scanf("%lf %lf %lf %lf",&L[i].a.x,&L[i].a.y, &L[i].b.x,&L[i].b.y); L[N].a.x=0;L[N].a.y=0;L[N].b.x=MaxL;L[N].b.y=0;arc[N]=0;N++; L[N].a.x=MaxL;L[N].a.y=0;L[N].b.x=MaxL;L[N].b.y=MaxL;arc[N]=PI*1.5;N++; L[N].a.x=MaxL;L[N].a.y=MaxL;L[N].b.x=0;L[N].b.y=MaxL;arc[N]=PI;N++; L[N].a.x=0;L[N].a.y=MaxL;L[N].b.x=0;L[N].b.y=0;arc[N]=PI*0.5;N++; for (int i=0;i<N;i++){ arc[i]=atan2(L[i].b.x-L[i].a.x, L[i].b.y-L[i].a.y); arc[i]=-arc[i]+PI*0.5; if (arc[i]<0.0)arc[i]+=PI+PI; } qs(0,N-1); int w; w=0; for (int i=0;i<N;i++){ if (!w || Abs(arc[i]-arc[w-1])>zero){ L[w]=L[i];arc[w]=arc[i];w++; }else if (!onLeft(L[i].a,L[w-1].a,L[i].b)) L[w-1]=L[i],arc[w-1]=arc[i]; } N=w; printf("%.1f\n",Half_Plane_Cross()); Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator