【BZOJ1007】水平可见直线

  把直线按照斜率排序，所有的可见线段画出来是个凸包。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=50010;
const double eps=1e-10;
 
struct Line
{
    double a,b;
    int ID;
    bool operator < (const Line &p) const {return a<p.a || (abs(a-p.a)<eps && b>p.b);}
}L[maxn];
typedef Line Node;
double GetX(Line x,Line y) {return (y.b-x.b)/(x.a-y.a);}
 
int Q[maxn],top;
int I[maxn];
double D[maxn];
int n;
 
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) scanf("%lf%lf",&L[i].a,&L[i].b),L[i].ID=i+1;
    sort(L,L+n);
    Q[top]=0;D[top]=-1e80;
    for (int i=1;i<n;i++)
    {
        if (abs(L[i].a-L[Q[top]].a)<eps) continue;
        D[++top]=GetX(L[i],L[Q[top-1]]);
        while (D[top]-D[top-1]<eps) D[--top]=GetX(L[i],L[Q[top-1]]);
        Q[top]=i;
    }
    for (int i=0;i<=top;i++) I[L[Q[i]].ID]=1;
    for (int i=1;i<=n;i++) if (I[i]) printf("%d ",i);
    return 0;
}