记录编号	158208	评测结果	AAAAAAAAAA
题目名称	Uyuw的音乐会	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.567 s
提交时间	2015-04-13 15:48:58	内存使用	2.13 MiB

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const int maxn=20100,_side=10000;
struct point{
	double x,y;
	point operator -(const point &a) const{
		return (point){x-a.x,y-a.y};
	}
	double operator *(const point &a) const{
		return x*a.y-a.x*y;
	}
}o,p[maxn];
struct list{
	point a,b;
	double angle;
	void calc(){
		angle=atan2(b.y-a.y,b.x-a.x);
	}
	void init(const double &x1,const double &y1,const double &x2,const double &y2){
		a=(point){x1,y1},b=(point){x2,y2};
	}
}lis[maxn],deq[maxn];
int n,m,cnt;
int dc(const double &x){
	if(x>eps) return 1;
	else if(x<-eps) return -1;
	return 0;
}
double cross(const point &a,const point &b,const point &c){
	return (b-a)*(c-a);
}
bool cmp(const list &a,const list &b){
	if(!dc(a.angle-b.angle)) return dc(cross(a.a,a.b,b.a))<0;
	return a.angle>b.angle;
}
point getp(const list &a,const list &b){
	double k1=cross(a.a,b.b,b.a);
	double k2=cross(a.b,b.a,b.b);
	point tmp=a.b-a.a;
	return (point){a.a.x+tmp.x*k1/(k1+k2),a.a.y+tmp.y*k1/(k1+k2)};
}
template<class T>bool _get(T &x){
	static int ch,gg;gg=0;
	while((ch=getchar())<40&&ch!=EOF);
	if(ch==EOF) return 0;if(ch==45) gg=1,x=0;else x=ch-48;
	while((ch=getchar())>47) x=x*10+ch-48;
	if(gg) x=-x;return 1;
}
double _calc(){
	double res=0.0;
	p[cnt+1]=p[1];
	for(int i=1;i<=cnt;i++)
		res+=cross(o,p[i],p[i+1]);
	return res;
}
void cut(){
	sort(lis+1,lis+n+1,cmp),m=1,cnt=0;
	for(int i=2;i<=n;i++)
		if(dc(lis[i].angle-lis[m].angle))
			lis[++m]=lis[i];
	deq[1]=lis[1],deq[2]=lis[2];
	int l=1,r=2;
	for(int i=3;i<=m;i++){
		while(l<r&&dc(cross(lis[i].a,lis[i].b,getp(deq[r],deq[r-1])))<0) r--;
		while(l<r&&dc(cross(lis[i].a,lis[i].b,getp(deq[l],deq[l+1])))<0) l++;
		deq[++r]=lis[i];
	}
	while(l<r&&dc(cross(deq[l].a,deq[l].b,getp(deq[r],deq[r-1])))<0) r--;
	while(l<r&&dc(cross(deq[r].a,deq[r].b,getp(deq[l],deq[l+1])))<0) l++; 
	if(l==r) return;
	for(int i=l;i<r;i++) p[++cnt]=getp(deq[i],deq[i+1]);
	if(r>l+1) p[++cnt]=getp(deq[r],deq[l]);
}
int main(){
	freopen("concert.in","r",stdin);
	freopen("concert.out","w",stdout);
	while(_get(n)){
		for(int i=1;i<=n;i++){
			_get(lis[i].a.x),_get(lis[i].a.y);
			_get(lis[i].b.x),_get(lis[i].b.y);
			lis[i].calc();
		}
		lis[n+1].init(0,0,_side,0),lis[n+1].calc();
		lis[n+2].init(0,_side,0,0),lis[n+2].calc();
		lis[n+3].init(_side,0,_side,_side),lis[n+3].calc();
		lis[n+4].init(_side,_side,0,_side),lis[n+4].calc();
		n+=4,cut(),printf("%.1lf\n",fabs(_calc())*0.5);
	}
}