[HNOI2008]水平可见直线

直线代入一点值相当于向量 (k,a) 和 (x, 1) 的点积，于是根据点积最大化思想直接跑上凸壳就对了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
const int MAXN = 50010;
typedef long long LL;
struct Point {
    int x, y, idx;
    explicit Point(int a = 0, int b = 0) { x = a, y = b; }
    inline bool operator < (const Point & b) const {
        return x == b.x ? y > b.y : x < b.x;
    }
    inline Point operator - (const Point & b) const {
        return Point(x - b.x, y - b.y);
    }
} ps[MAXN];
LL cross(const Point & a, const Point & b) {
    return static_cast<LL> (a.x) * b.y - static_cast<LL> (a.y) * b.x;
}
int n, hav[MAXN];
int st[MAXN], top;
void solve() {
    std::sort(ps + 1, ps + 1 + n);
    st[1] = 1; st[top = 2] = 2;
    for (int i = 3; i <= n; ++i) {
        while (top >= 2 && cross(ps[st[top]] - ps[st[top - 1]], ps[i] - ps[st[top]]) >= 0) --top;
        st[++top] = i;
    }
    for (int i = 1; i <= top; ++i) hav[ps[st[i]].idx] = true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) 
        scanf("%d%d", &ps[i].x, &ps[i].y), ps[i].idx = i;
    solve();
    for (int i = 1; i <= n; ++i) if (hav[i]) printf("%d ", i);
    putchar(10);
    return 0;
}