P3194 [HNOI2008]水平可见直线

给一个不是半平面交的做法（

首先去重，斜率相同的只有截距较大者可见，因此下面的讨论中斜率各不相同。

假设有三条直线 l_1, l_2, l_3，考虑如果 l_2 被遮挡，这三条直线应满足什么条件。

若 l_2 是三者中斜率最大或者最小的，显然其不会被遮挡，所以我们不妨设 A_1 < A_2 < A_3。如图所示：

可以发现，记 l_1 \cap l_3 = P(x_0, y_0)，如果 A_1x_0 + B_1 \geq A_2 x_0 + B_2，则 l_2 被遮挡，否则 l_2 不被 l_1 和 l_3 遮挡。

接下来搞一波式子：

于是我们得到了这个红色的式子，记 P_i=(A_i, B_i)，那么上面的式子可以理解为：若 P_1 到 P_3 的斜率大于 P_1 到 P_2 的斜率，那么 l_2 被遮挡。如图所示，下图中 l_2 会被遮挡。

因此可见的直线应满足其对应的点 P_i 在点集 \{P_i\} 构成的上凸壳上。跑 Andrew 算法就可以了

实际上凸包和半平面交本身就是对偶问题所以这和半平面交其实是同一种做法。

#include<bits/stdc++.h>
using namespace std;

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 5e4 + 5;
const double eps = 1e-8;
int n, top;
struct Vector {
    long long x, y;
    int id;
    Vector(long long a = 0, long long b = 0, long long c = 0) { x = a, y = b, id = c; }
    Vector operator +(Vector b) const { return Vector(x + b.x, y + b.y); }
    Vector operator -() const { return Vector(-x, -y); }
    Vector operator -(Vector b) { return *this + (-b); }
    double operator &(Vector b) { return x * b.y - y * b.x; }
} p[N], bin[N];

int main() {
    n = get();
    for(int i = 1; i <= n; i++) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        p[i] = Vector(x, y, i);
    }
    sort(p + 1, p + 1 + n, [](Vector a, Vector b){ return a.x == b.x? a.y > b.y : a.x < b.x; });
    bin[1] = p[1], top = 1;
    for(int i = 2; i <= n; i++) {
        if(p[i].x == p[i - 1].x) continue;
        while(top > 1 && ((bin[top] - bin[top - 1]) & (p[i] - bin[top])) >= 0) --top;
        bin[++top] = p[i];
    }
    sort(bin + 1, bin + 1 + top, [](Vector a, Vector b){ return a.id < b.id; });
    for(int i = 1; i <= top; i++) 
        printf("%d ", bin[i].id);
    return 0;
}