记录编号	117752	评测结果	AAAAAAAAAA
题目名称	Uyuw的音乐会	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.972 s
提交时间	2014-08-31 14:03:32	内存使用	1.23 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<iomanip>
using namespace std;
const double eps=1e-10,pi=acos(-1.0);
const int SIZEN=20010;
class POINT{
public:
	double x,y;
};
double cross(POINT a,POINT b){
	return a.x*b.y-b.x*a.y;
}
class HPL{//半平面
public:
	double a,b,c;//ax+by<=c
	double pa;//极角
	void print(void){cout<<"极角:"<<pa<<" 不等式:";cout<<a<<"x + "<<b<<"y <= "<<c<<endl;}
};
void print(HPL h){h.print();}
void print(POINT p){cout<<"("<<p.x<<" "<<p.y<<")";}
bool cmp(HPL s,HPL t){
	return s.pa<t.pa;
}
bool inside(POINT p,HPL h){
	return p.x*h.a+p.y*h.b<h.c-eps;
}
POINT inter(HPL s,HPL t){//交点,要求s,t的极角不同
	POINT ans;
	ans.x=(s.c*t.b-t.c*s.b)/(s.a*t.b-t.a*s.b);
	ans.y=(s.c*t.a-t.c*s.a)/(s.b*t.a-t.b*s.a);
	return ans;
}
void HPL_Intersection(HPL h[],int N,deque<HPL> &Q){
	//要求此时已经计算出了所有半平面的极角
	//Q中将返回约束了核的那些半平面
	//半平面是h[1]~h[N]
	//将所有半平面,极角相同者取约束最紧的
	sort(h+1,h+1+N,cmp);
	int tot=0;
	for(int i=1;i<=N;i++){
		if(tot==0||fabs(h[tot].pa-h[i].pa)>eps) h[++tot]=h[i];
		else if(h[i].c<h[tot].c) h[tot]=h[i];
	}
	N=tot;
	Q.clear();
	for(int i=1;i<=N;i++){
		//从队列两端删除
		//顺序不能错!
		while(Q.size()>=2&&!inside(inter(Q.back(),Q[Q.size()-2]),h[i])) Q.pop_back();
		while(Q.size()>=2&&!inside(inter(Q[0],Q[1]),h[i])) Q.pop_front();
		Q.push_back(h[i]);
	}
	while(Q.size()>=2&&!inside(inter(Q.back(),Q[Q.size()-2]),Q[0])) Q.pop_back();
}
int N;
HPL H[SIZEN];
deque<HPL> Q;
POINT P[SIZEN];
void work(void){
	HPL_Intersection(H,N,Q);
	if(Q.size()<=2){
		printf("0.0\n");
		return;
	}
	for(int i=1;i<Q.size();i++) P[i+1]=inter(Q[i-1],Q[i]);
	P[1]=inter(Q[0],Q.back());
	double ans=0;
	int n=Q.size();
	for(int i=1;i<n;i++) ans+=cross(P[i],P[i+1]);
	ans+=cross(P[n],P[1]);
	ans/=2.0;
	printf("%.1lf\n",ans);
}
void assign(HPL &h,double x1,double y1,double x2,double y2){
	h.pa=atan2(y1-y2,x1-x2);
	if(h.pa<0) h.pa+=2*pi;
	h.a=y2-y1,h.b=x1-x2,h.c=x1*y2-x2*y1;
}
bool init(void){
	if(scanf("%d",&N)==EOF) return false;
	double x1,y1,x2,y2;
	for(int i=1;i<=N;i++){
		scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		assign(H[i],x1,y1,x2,y2);
	}
	assign(H[++N],0,10000,0,0);
	assign(H[++N],0,0,10000,0);
	assign(H[++N],10000,0,10000,10000);
	assign(H[++N],10000,10000,0,10000);
	return true;
}
int main(){
	freopen("concert.in","r",stdin);
	freopen("concert.out","w",stdout);
	while(init()) work();
	return 0;
}