Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——攻下第一个半平面交

Posted by fanhqme at 2009-12-20 15:20:56 on Problem 2451
计算几何,细心大胆。

使用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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator