记录编号	158217	评测结果	AAAAAAAAAA
题目名称	Uyuw的音乐会	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.702 s
提交时间	2015-04-13 16:16:10	内存使用	2.12 MiB

/****************************************\
* Author : ztx
* Title  : [poj] 2451 Uyuw's Concert
* ALG    : 半平面交O(nlog)学习
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cmath>

#define  maxn  20010LL
#define  infi  10000LL
#define  eps   1e-10
inline int sign(double x) { return (x>eps)-(x<-eps) ; }

struct POINT {
	double x,y;
	POINT operator - (const POINT& b) const
	{ return (POINT){x-b.x,y-b.y} ; }
	double operator * (const POINT& b) const
	{ return x*b.y-b.x*y; }
} p[maxn],o ;
typedef POINT VECTOR ;

struct LINE {
	POINT a , b ; double ang ;
	void init(double x,double y,double xx,double yy)
	{ a.x=x;a.y=y;b.x=xx;b.y=yy; }
} L[maxn] , q[maxn] ;
int n , m , cnt ;

inline double Cross(POINT a,POINT b,POINT c)
{ return (b-a)*(c-a) ; }

inline POINT GetCross(LINE& a,LINE& 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,ans;
	ans.x=a.a.x+tmp.x*k1/(k1+k2) ;
	ans.y=a.a.y+tmp.y*k1/(k1+k2) ;
	return ans ;
}

inline bool cmp(const LINE& a,const LINE& b)
{ return sign(a.ang-b.ang) ? a.ang>b.ang : sign(Cross(a.a,a.b,b.a))<0 ; }

inline void Cut() {
int i , l , r ;
	std::sort(L+1,L+n+1,cmp) ;
	m = 1 ;
	Rep (i,2,n) if (sign(L[i].ang-L[m].ang)) L[++m] = L[i] ;
	q[l=1]=L[1],q[r=2]=L[2] ;
	Rep (i,3,m) {
		while (l<r && sign(Cross(L[i].a,L[i].b,GetCross(q[r],q[r-1])))<0) r-- ;
		while (l<r && sign(Cross(L[i].a,L[i].b,GetCross(q[l],q[l+1])))<0) l++ ;
		q[++r] = L[i] ;
	}
	while (l<r && sign(Cross(q[l].a,q[l].b,GetCross(q[r],q[r-1])))<0) r-- ;
	while (l<r && sign(Cross(q[r].a,q[r].b,GetCross(q[l],q[l+1])))<0) l++ ;
	if (l == r) return ;
	cnt = 0 ;
	Rep (i,l,r-1) p[++cnt] = GetCross(q[i],q[i+1]) ;
	if (r-1>l) p[++cnt] = GetCross(q[l],q[r]) ;
}

inline double GetArea() {
int i ;
	double ret = 0.0 ;
	p[cnt+1] = p[1] ;
	Rep (i,1,cnt) ret += Cross(o,p[i],p[i+1]) ;
	return ret ;
}

int main() {
int i ;
	#define READ
	#ifdef  READ
		freopen("concert.in" ,"r",stdin ) ;
		freopen("concert.out","w",stdout) ;
	#endif
	while (scanf("%d",&n)!=EOF && n) {
		Rep (i,1,n) {
			scanf("%lf%lf%lf%lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y) ;
			L[i].ang = atan2(L[i].b.y-L[i].a.y,L[i].b.x-L[i].a.x) ;
		}
		L[n+1].init(0,0,infi,0) ;
		L[n+2].init(0,infi,0,0) ;
		L[n+3].init(infi,0,infi,infi) ;
		L[n+4].init(infi,infi,0,infi) ;
		Rep (i,n+1,n+4) L[i].ang=atan2(L[i].b.y-L[i].a.y,L[i].b.x-L[i].a.x) ;
		n += 4 ;
		Cut() ;
		printf("%.1lf\n", (double)fabs(GetArea())*0.5) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}