| ||||||||||
| 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