记录编号	396622	评测结果	AAAAAAAAAA
题目名称	Uyuw的音乐会	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.598 s
提交时间	2017-04-18 21:34:34	内存使用	2.43 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int SIZEN = 20010;
const double eps = 1e-7;
typedef struct POINT{
	double x,y;
	POINT(double x_=0,double y_=0):x(x_),y(y_){}
	POINT operator - (const POINT &A){return POINT(x-A.x,y-A.y);}
	POINT operator + (const POINT &A){return POINT(x+A.x,y+A.y);}
	POINT operator * (const double &A){return POINT(x*A,y*A);}
}Vector;
struct LINE{
	POINT p;
	Vector v;
	double ang;
	LINE(){}
	LINE(POINT p_,Vector v_):p(p_),v(v_){ang = atan2(v.y,v.x);}
	bool operator < (const LINE &A)const{return ang < A.ang;}
};
int dcmp(double x){
	if(fabs(x) < eps)return 0;
	return x > 0?1:-1;
}
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
bool OnLeft(LINE A,POINT P){return dcmp(Cross(A.v,P-A.p)) >= 0;}
POINT SegmentIntersection(LINE A,LINE B){
	Vector v = A.p - B.p;
	double t = Cross(B.v,v)/Cross(A.v,B.v);
	return A.p+A.v*t;
}

LINE L[SIZEN],q[SIZEN];
POINT p[SIZEN],ch[SIZEN];
int front,back,m;
void HalfPlanIntersection(LINE *L,int N,POINT *ch,int &m){
	sort(L+1,L+1+N);
	q[front = back=1] = L[1];
	for(int i = 2;i <= N;i++){
		while(front!=back && !OnLeft(L[i],p[back-1]))back--;
		while(front!=back && !OnLeft(L[i],p[front]))front++;
		q[++back] = L[i];
		if(dcmp(Cross(q[back].v,q[back-1].v)) == 0){
			back--;
			if(!OnLeft(L[i],q[back].p))q[back] = L[i];
		}
		if(front!=back)p[back-1] = SegmentIntersection(q[back],q[back-1]);
	}
	while(front!=back && !OnLeft(q[front],p[back-1]))back--;
	p[back] = SegmentIntersection(q[front],q[back]);
	for(int i = front;i <= back;i++)ch[++m] = p[i];
}
int main(){
	freopen("concert.in","r",stdin);
	freopen("concert.out","w",stdout);
	int N;
	while(scanf("%d",&N)!=EOF){m = 0;
		for(int i = 1;i <= N;i++){
			double x1,x2,y1,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			L[i] = LINE(POINT(x1,y1),POINT(x2,y2)-POINT(x1,y1));
		}
		L[++N] = LINE(POINT(0,0),Vector(1,0));
		L[++N] = LINE(POINT(10000,0),Vector(0,1));
		L[++N] = LINE(POINT(10000,10000),Vector(-1,0));
		L[++N] = LINE(POINT(0,10000),Vector(0,-1));
		HalfPlanIntersection(L,N,ch,m);
		double ans = 0;
		for(int i = 2;i < m;i++){
			ans += Cross(ch[i]-ch[1],ch[i+1]-ch[1]);
		}
		printf("%.10f\n",fabs(ans/2));
	}
}