[HNOI2008]水平可见直线
1 2 3 4 5 6 7 8 9 10 11 12 | /****************************************\* 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 :\****************************************/ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | /****************************************\* 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 500010LLstruct 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 ;} |
评论 (0)