ztx's Blog

/****************************************\
* Author : ztx
* Title  : poj 3335 Rotating Scoreboard
* ALG    : 计算几何 半平面交 多边形内核
* CMT    : 这是一个n^n算法
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : poj 3335 Rotating Scoreboard
* 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} ; }
	int 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 ; }

int n , size , top ;

POINT Intersect(POINT a , POINT b , POINT c , POINT d) {
	/* 传进四个点时,保证有交点 */
	POINT ret ;
	if (a.x == b.x) {
		ret.x = a.x ; ret.y = (c.y+d.y)/2.0 ;
	} else if (c.x == d.x) {
		ret.x = c.x ; ret.y = (a.y+b.y)/2.0 ;
	} 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 */
}

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 ;
}

bool Solve() {
	for (int i = 1 ; i <= n ; i ++ )
		Cut(points[i] , points[i+1]) ;
	return size > 0 ;
}

int main() {
int T , i ;
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d", &T ) ;
	while (T --) {
		scanf("%d", &n ) ;
		for (i = 1 ; i <= n ; i ++ )
			scanf("%lf%lf", &points[i].x , &points[i].y) ;
		points[n+1] = points[1] ;
		points[0] = points[n] ;
		for (i = n+1 ; i >= 0 ; i -- ) p[i] = points[i] ;
		size = n ;
		if (Solve()) puts("YES") ;
		else puts("NO") ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}