BZOJ1007: [HNOI2008]水平可见直线

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1007

Solution

裸单调栈。。
就是先按斜率排序，每次进栈判断是否将栈顶覆盖即可，判断是否覆盖可以根据两条直线与栈中直线交点的x坐标大小即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll int
#define N 50005
#define eps 1e-8
using namespace std;
struct data{
    double k,b;
    ll id;
}a[N],stack[N];
ll n,top,vis[N];
bool cmp(data x,data y){
    if (fabs(x.k-y.k)<eps) return x.b<y.b;
    else return x.k<y.k;
}
double cross(data x,data y){
    return (y.b-x.b)/(x.k-y.k);
}
void add(data x){
    while (top){
        if (fabs(stack[top].k-x.k)<eps) top--;
        else if (top>1&&cross(x,stack[top-1])<=cross(stack[top],stack[top-1])) top--;
        else break;
    }
    stack[++top]=x;
}
int main(){
    scanf("%d",&n);
    for (ll i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].k,&a[i].b);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for (ll i=1;i<=n;i++)
        add(a[i]);
    for (ll i=1;i<=top;i++)
        vis[stack[i].id]=1;
    for (ll i=1;i<=n;i++)
        if (vis[i]) printf("%d ",i);
}