poj2451——Uyuw's Concert//半平面交

<半平面交>资料详见：朱泽圆06年论文。

半平面交思想：

1，对半平面预先处理，求极角并排序、去重。

2，在凸多边形交里面，根据论文所讲，反复做删去、加入半平面的操作。

具体实现，可以参考http://hi.baidu.com/lgq1205/blog/item/8e7a99fb31586b879f514646.html 代码有注释，讲得很好！

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=20010;
const int bound=10000;
const double esp= 1e-10;
class point
{
public:
	double x,y;
};
class node
{
public:
	point a,b;
};
node pp[maxn];
int cnt,id[maxn],n;
double at[maxn];
int q[maxn*2],front,rear,dg;
point dpg[maxn];
void add(double x1,double y1,double x2,double y2)
{
	pp[cnt].a.x =x1;pp[cnt].a .y =y1;
	pp[cnt].b.x =x2;pp[cnt++].b.y =y2;
}
void read()
{
	scanf("%d",&n);
	cnt=0;double x1,x2,y1,y2;
	for(int i=0;i<n;i++)
	{
		scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		add(x1,y1,x2,y2);
	}
	n+=4;
	add(0,0,bound,0);
	add(bound,0,bound,bound);
	add(bound,bound,0,bound);
	add(0,bound,0,0);
}
int is0(double a)//与0比较
{
	if(a<=esp&&a>=-esp) return 0;
	if(a>esp) return 1;
	return -1;
}
double det(double x1,double y1,double x2,double y2)
{
	return x1*y2-x2*y1;
}
//p2是否p0->p1的左边  
double ana(point p0,point p1,point p2)//叉积  大于0在左边
{
	return det(p1.x-p0.x ,p1.y -p0.y ,p2.x -p0.x ,p2.y -p0.y );
}
bool cmp(int a,int b)
{	
	if(at[a]<at[b]) return true;
	if(is0(at[a]-at[b])==0)//平行的时候
		if(is0(ana(pp[b].a,pp[b].b,pp[a].a ))>=0) return true;//a在"左边时",交换位置
	return false;
}
void deal()//处理半平面
{
	for(int i=0;i<n;i++)
	{
		at[i]=atan2(pp[i].b.y-pp[i].a.y ,pp[i].b.x -pp[i].a.x );//求极角
		id[i]=i;
	}
	sort(id,id+n,cmp);//极角排序
	int temp=1;
	for(int i=1;i<n;i++)//去重
		if(is0(at[id[i-1]]-at[id[i]])!=0)  id[temp++]=id[i];
	n=temp;
}
point APP(node &t1,node &t2)//求交点函数
{
	double d1,d2;
	point s1,e1,s2,e2;
	s1=t1.a ;e1=t1.b ;s2=t2.a ;e2=t2.b ;
	point temp;
	d1=ana(s2,e1,s1);d2=ana(e1,e2,s1);
	temp.x =(s2.x *d2+e2.x *d1)/(d2+d1);
	temp.y =(s2.y *d2+e2.y *d1)/(d2+d1);
	return temp;
}
bool judge(int x,int y,int now)//判断顶端交点是否在半平面外  
{
	point temp=APP(pp[x],pp[y]);
	double d=ana(pp[now].a,pp[now].b,temp);
	if(is0(d)<0) return true;
	return false;
}
void solve()//凸多边形交
{
	int i;
	front=0;rear=1;
	q[0]=id[0];q[1]=id[1];
	for(i=2;i<n;i++)
	{
		while(front<rear&&judge(q[rear-1],q[rear],id[i]))
			rear--;
		while(front<rear&&judge(q[front],q[front+1],id[i]))
			front++;
		q[++rear]=id[i];
	}
	while(front<rear&&judge(q[rear-1],q[rear],q[front]))
		rear--;
	while(front<rear&&judge(q[front],q[front+1],q[rear]))
		front++;
	q[++rear]=q[front];//算面积的时候 应将某条边多算一次
	dg=0;
	for(i=front+1;i<=rear;i++)
		dpg[dg++]=APP(pp[q[i-1]],pp[q[i]]);
}
double  area()//叉积求面积
{
	double ans=0;
	for(int i=0;i<dg;i++)
		ans+=dpg[i].x*dpg[(i+1)%dg].y -dpg[(i+1)%dg].x *dpg[i].y ;
	ans=fabs(ans)/2.0;
	return ans;
}
int main()
{
	read();//读入数据
	deal();//半面交处理
	solve();//凸多边形交
	printf("%.1f\n",area());
	return 0;
}