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

/****************************************\
* Author : ztx
* Title  : [HNOI2008]水平可见直线
* ALG    : 计算几何
* CMT    :
* 要维护的是一个下凸线一样的东西。即从左到右的交点（左）右边的直线是斜率越来越大的。
* 所以我们可以按斜率从小到大排序后。用一个栈来这样维护。
* 每次新加一条直线k,设当前栈顶直线为stack[top]=j,栈顶前一条直线为stack[top-1]=i,
* 则若(k,j)的交点在(i,j）交点的左边或重合，则j必是被k与i及之前的直线所完全覆盖的，
* 所以把j pop 出。直到不能再pop为止，再把k加入栈中
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [HNOI2008]水平可见直线
* ALG    : 计算几何
* CMT    :
* 要维护的是一个下凸线一样的东西。即从左到右的交点（左）右边的直线是斜率越来越大的。
* 所以我们可以按斜率从小到大排序后。用一个栈来这样维护。
* 每次新加一条直线k,设当前栈顶直线为stack[top]=j,栈顶前一条直线为stack[top-1]=i,
* 则若(k,j)的交点在(i,j）交点的左边或重合，则j必是被k与i及之前的直线所完全覆盖的，
* 所以把j pop 出。直到不能再pop为止，再把k加入栈中
* Time   :
\****************************************/

#include <cstdio>
#include <algorithm>

#define  maxn  500010LL

struct LINE { int k , b , id ; } lines[maxn] ;

int n , i , top = 0 , sta[maxn] ;
bool flag[maxn] = {0} ;

bool Cmp(const LINE& a , const LINE& b) {
	if (a.k == b.k) return a.b > b.b ; return a.k < b.k ;
}

double CrossX(LINE a , LINE b) { return (double)(b.b-a.b)/(double)(a.k-b.k) ; }

double x1 , x2 ;
bool Check(LINE a , LINE b , LINE c) {
	x1 = CrossX(a , b) ; x2 = CrossX(b , c) ;
	if (x1 <= x2) return true ;
	else return false ;
}

int main() {
//	#define READ
	#ifdef  READ
		freopen(".in" ,"r",stdin ) ;
		freopen(".out","w",stdout) ;
	#endif
	scanf("%d", &n ) ;
	for (i = 1 ; i <= n ; i ++ )
		scanf("%d%d", &lines[i].k , &lines[i].b ) , lines[i].id = i ;
	std::sort(lines+1 , lines+n+1 , Cmp) ;
	for (i = 1 ; i <= n ; i ++ ) {
		if (lines[i].k == lines[i-1].k) continue ;
		while (top>1 && Check(lines[i],lines[sta[top]],lines[sta[top-1]])) flag[lines[sta[top--]].id] = false ;
		sta[++top] = i ; flag[lines[i].id] = true ;
	}
	for (i = 1 ; i <= n ; i ++ ) if (flag[i]) printf("%d ", i ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}