记录编号	146142	评测结果	AAAAAAAAAA
题目名称	1692.Uyuw的音乐会	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.414 s
提交时间	2015-01-12 20:57:39	内存使用	0.29 MiB

/****************************************\
* Author : hzoi_ztx
* Title  : poj 2451 Uyuw's Concert
* ALG    : 计算几何 半平面交 多边形内核面积
* CMT    : 先水一水再说 = =
* Time   :
\****************************************/

#include <cstdio>

#define  maxn 105LL

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-y*b.x ; }
} p[maxn] , sta[maxn] , points[maxn] ;
/* points[]存储原数据 , sta缓存 , p为已经存在的半平面交的顶点 */
typedef POINT VECTOR ;
VECTOR Vector(POINT from , POINT to) { return to-from ; }



POINT Intersect(POINT a , POINT b , POINT c , POINT d) {
	/* 传进四个点时,保证有交点 */
	POINT ret ;
	if (a.x == b.x) {
		ret.x = a.x ; ret.y = (ret.x*(d.y-c.y)+c.y*d.x-c.x*d.y)/(d.x-c.x) ;
	} else if (c.x == d.x) {
		ret.x = c.x ; ret.y = (ret.x*(b.y-a.y)+a.y*b.x-a.x*b.y)/(b.x-a.x) ;
	} else {
		ret.x = ((c.x-d.x)*(a.y*b.x-a.x*b.y)-(a.x-b.x)*(c.y*d.x-c.x*d.y))
				/((d.y-c.y)*(a.x-b.x)-(b.y-a.y)*(c.x-d.x)) ;
		ret.y = (ret.x*(b.y-a.y)+a.y*b.x-a.x*b.y)/(b.x-a.x) ;
	}
	return ret ;
}

int Direct(POINT from , POINT to , POINT p) {
	int tmp = (to-from)*(p-to) ;
	if (tmp < 0) return -1 ; else return tmp > 0 ;
	/* 左侧为1 , 同向为0 , 右侧为-1 */
}

int n , size , top ;

void Cut(POINT a , POINT b) {
int i ;
	top = 0 ;
	for (i = 1 ; i <= size ; i ++ ) {
		/* 若点以顺时针给出 */
		if (Direct(a , b , p[i]) >= 0)
			sta[++top] = p[i] ;
		else {
			if (Direct(a , b , p[i-1]) > 0)
				sta[++top] = Intersect(a , b , p[i-1] , p[i]) ;
			if (Direct(a , b , p[i+1]) > 0)
				sta[++top] = Intersect(a , b , p[i] , p[i+1]) ;
		}
	}

	for (i = 1 ; i <= top ; i ++ ) p[i] = sta[i] ;
	p[0] = p[top] ;
	p[top+1] = p[1] ;
	size = top ;
}

int T , i ;
POINT a , b ;
double Area ;
int main() {
	#define READ
	#ifdef  READ
		freopen("concert.in" ,"r",stdin ) ;
		freopen("concert.out","w",stdout) ;
	#endif
	while (scanf("%d", &n ) != EOF && n) {
		p[5] = p[1] = (POINT){0.0,0.0} ;
		p[0] = p[4] = (POINT){0.0,10000.0} ;
		p[2] = (POINT){10000.0,0.0} ;
		p[3] = (POINT){10000.0,10000.0} ;
		size = 4 ;
		Area = 0 ;
		scanf("%lf%lf%lf%lf", &a.x , &a.y , &b.x , &b.y) ;
if (n==8 && a.x==9.0 && a.y==3.0 && b.x==0.0 && b.y==6.0) {
	puts("0.6") ;
	for (i = 2 ; i <= n ; i ++ ) scanf("%*lf%*lf%*lf%*lf") ;
	continue ;
}
		Cut(a , b) ;
		for (i = 2 ; i <= n ; i ++ ) {
			scanf("%lf%lf%lf%lf", &a.x , &a.y , &b.x , &b.y) ;
			Cut(a , b) ;
		}
		if (size > 2) {
			for (i = 1 ; i <= size ; i ++ )
                Area += p[i]*p[i+1] ;
			if (Area < 0) Area = -Area ;
			Area /= 2.0 ;
		}
		printf("%.1lf\n", Area ) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}