[BZOJ1007][HNOI2008]水平可见直线

这个题我一开始看的时候有凸包的感觉，无奈对算法掌握不是很熟悉，没有成功的解决，看了题解才知道这个题竟然如此的水，就是一个凸包的模板。

code:

#include <cstdio>
#include <cmath>
#include <algorithm>

typedef double LL; // mark
const int N = 50000 + 10;
const double eps = 1e-10;

struct line {
    LL k, b;
    line (LL x = 0, LL y = 0) : k(x), b(y) {}
} l[N];
int stl, s[N], p[N];
int n;

LL cross(line a, line b, line c) { // 判断a与b的交点是否在b与c的交点的左侧 
    return (b.b - a.b) * (b.k - c.k) - (a.k - b.k) * (c.b - b.b); // mark
}

bool cmp(int a, int b) {
    if (fabs(l[a].k - l[b].k) < eps) return l[a].b < l[b].b ;
    else return l[a].k < l[b].k;
}

bool check(int a, int b, int c) {
    double res = cross(l[a], l[b], l[c]);
    return fabs(res) <= eps || res <= 0;
}

inline void cvx() { // mark
    std::sort(p+1, p+n+1, cmp);
    for (int i = 1; i <= n; ++i) {
        while (stl) {
            if (fabs(l[p[i]].k - l[s[stl]].k) < eps) stl--;
            else if (stl>1 && check(p[i], s[stl], s[stl-1])) stl--;
            else break;
        }
        s[++stl] = p[i];
    }
    
}

int main() {
    scanf("%d", &n);
    if (n == 1) { puts("1 "); return 0; }
    for (int i = 1; i <= n; ++i) {
        scanf("%lf%lf", &l[i].k, &l[i].b);
        p[i] = i;
    }
    
    cvx();
    std::sort(s+1, s+1+stl);
    for (int i = 1; i <= stl; ++i) printf("%d ", s[i]);
    return 0;
}

这个题前后也是折腾了很久，一开始cross那里写反了，gg*1；后来发现没有用double，gg*2；再后来没有写实数比较，gg*3；最后才发现自己没有处理好斜率相同的情况，gg*4，前前后后交了5次，这才改好了这个题，仔细回想一下，如果是考试的话，我大概就已经gg*inf了，以后对于这种细节题还是要仔细。

以及这个凸包的写法简直太好了，无需提前入栈前两个元素，优美。

[BZOJ1007][HNOI2008]水平可见直线

原文：https://www.cnblogs.com/wyxwyx/p/bzoj1007.html