记录编号	369985	评测结果	AAAAAAAAAA
题目名称	Uyuw的音乐会	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.665 s
提交时间	2017-02-12 11:15:24	内存使用	9.45 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long double db;
const db pi=acos(-1.0);
const int N=1e5+10;
struct pt{
	db x,y;
	pt(db X=0,db Y=0){x=X;y=Y;}
	pt operator + (const pt a)const{return pt(x+a.x,y+a.y);}
	pt operator - (const pt a)const{return pt(x-a.x,y-a.y);}
	db operator ^ (const pt a)const{return x*a.y-y*a.x;}
};
struct line{
	db a,b,c,angle;
	line(db A=0,db B=0,db C=0){
		a=A;b=B;c=C;
		A=abs(a);
		if (A>0) a/=A,b/=A,c/=A;
		angle=atan2(b,a);
	}
	line(pt x,pt y){
		a=x.y-y.y;b=y.x-x.x;c=x^y;
		db A=abs(a);
		if (A>0) a/=A,b/=A,c/=A;
		angle=atan2(b,a);
	}
	bool operator < (const line &x)const{
		return angle==x.angle?c<x.c:angle<x.angle;
	}
}l[N],q[N];
pt point(line x,line y){
	db d=x.a*y.b-x.b*y.a;
	return pt((x.b*y.c-y.b*x.c)/d,(x.c*y.a-x.a*y.c)/d);
}
bool check(line x,line y,line z){
	pt p=point(x,y);
	return z.a*p.x+z.b*p.y+z.c<0;
}
int n;
int main()
{
	freopen("concert.in","r",stdin);
	freopen("concert.out","w",stdout);
	while (~scanf("%d",&n)){
		for (int i=1;i<=n;i++){
			pt L,R;
			scanf("%Lf%Lf%Lf%Lf",&L.x,&L.y,&R.x,&R.y);
			l[i]=line(L,R);
		}
		int head=1,tail=0;
		l[++n]=line(1,0,0);
		l[++n]=line(-1,0,1e4);
		l[++n]=line(0,1,0);
		l[++n]=line(0,-1,1e4);
		sort(l+1,l+n+1);
		l[0].angle=-1e10;
		for (int i=1;i<=n;i++)
		if (l[i].angle!=l[i-1].angle){
			for (;head<tail&&check(q[tail-1],q[tail],l[i]);tail--);
			for (;head<tail&&check(q[head],q[head+1],l[i]);head++);
			q[++tail]=l[i];
		}
		for (;head<tail&&check(q[tail-1],q[tail],q[head]);tail--);
		for (;head<tail&&check(q[head],q[head+1],q[tail]);head++);
		db ans=0;
		pt Begin=point(q[head],q[tail]);
		for (int i=head+1;i<tail;i++){
			pt L=point(q[i-1],q[i]),R=point(q[i],q[i+1]);
			ans+=abs((Begin-L)^(R-L))/2;
		}
		printf("%.1Lf\n",ans);
	}
	return 0;
}