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$ 遮挡。 接下来搞一波式子： $$ A_1x_0 + B_1 = A_3x_0 + B_3 \Rightarrow x_0 = \frac{B_3 - B_1}{A_1 - A_3} $$ $$ A_1\frac{B_3 - B_1}{A_1 - A_3} + B_1 \geq A_2\frac{B_3 - B_1}{A_1 - A_3} + B_2 \Rightarrow \color{red}{\frac{B_3 - B_1}{A_3 - A_1} \geq \frac{B_2 - B_1}{A_2 - A_1}} $$ 于是我们得到了这个红色的式子，记 $P_i=(A_i, B_i)$，那么上面的式子可以理解为：若 $P_1$ 到 $P_3$ 的斜率大于 $P_1$ 到 $P_2$ 的斜率，那么 $l_2$ 被遮挡。如图所示，下图中 $l_2$ 会被遮挡。  因此可见的直线应满足其对应的点 $P_i$ 在点集 $\{P_i\}$ 构成的上凸壳上。跑 Andrew 算法就可以了 ~~实际上凸包和半平面交本身就是对偶问题所以这和半平面交其实是同一种做法。~~ ```cpp #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; } ```