【bzoj1007】[HNOI2008]水平可见直线 单调栈

Description

在xoy直角坐标平面上有n条直线L1,L2,…Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的. 例如,对于直线: L1:y=x; L2:y=-x; L3:y=0 则L1和L2是可见的,L3是被覆盖的. 给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input3-1 01 00 0Sample Output1 2HINTSource

来自胡策的一道题…

先说一下我的60分n^2算法…

对于一条直线，把它与其它直线作差，用得到的差值来确定x的取值范围，若最后x不可能存在，则这条直线肯定不是答案。

满分做法：

可以观察到，我们要求的是一个凹形的图形。

首先，我们先按k升序为第一关键字，，b降序为第二关键字，然后用一个单调栈来维护这些直线。

若当前直线i能完全覆盖栈顶直线s[top]，则i与s[top]的交点一定在s[top]与s[top-1]的交点左边或者重合。若在它左边或者重合，则弹出栈顶，直到交点在右边后，扔进栈里。最后栈中元素就是答案。

bzoj没有卡此题的精度。

;const int size=1000010;struct haha{double k,b;int id;}l[size];bool operator <(haha a,haha b){if(a.k!=b.k) return a.k<b.k;return a.b>b.b;}double getpos(haha a,haha b){return (b.b-a.b)/(a.k-b.k);}int s[size];bool ans[size];int main(){int n;scanf(“%d”,&n);for(int i=1;i<=n;i++){scanf(“%lf%lf”,&l[i].k,&l[i].b);l[i].id=i;}sort(l+1,l+1+n);int top=1;s[1]=1;for(int i=2;i<=n;i++){if( l[i].k-l[i-1].k < 1e-8) continue;while(top > 1&& getpos(l[i],l[s[top]]) <= getpos(l[s[top]],l[s[top-1]]) ) top–;s[++top]=i;}for(int i=1;i<=top;i++) ans[l[s[i]].id]=1;for(int i=1;i<=n;i++)if(ans[i])printf(“%d “,i);return 0;}

到一个新的环境去欣赏去看去听，