/****************************************\
* 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 ;
}

• 相关文章
• 全局相关文章