洛谷P3194 [HNOI2008]水平可见直线 题解

题目链接：P3194 [HNOI2008]水平可见直线

题意：在$ x-y$ 直角坐标平面上有 $n$ 条直线 $L_1,L_2,…L_n$，若在 $y$ 值为正无穷大处往下看，能见到 $L_i$ 的某个子线段，则称 $L_i$ 为可见的，否则 $L_i$ 为被覆盖的。 例如，对于直线: $L_1:y=x$; $L_2:y=-x$; $L_3:y=0$; 则 $L_1$ 和 $L_2$ 是可见的，$L_3$ 是被覆盖的。给出 $n$ 条直线，表示成 $y=Ax+B$ 的形式($|A|,|B| \le 500000$)，且 $n$ 条直线两两不重合，求出所有可见的直线。

一条直线C被另外两条直线A和B所覆盖

它的充分必要条件为直线C在A,B交点处的值更小一些

反之，直线C也可能对答案有贡献

那么交点的坐标是什么呢？

$$A_1x+B_1=A_2x+B_2\\ x=\dfrac{B_2-B_1}{A_1-A_2}$$

则

$$A_1\dfrac{B_2-B_1}{A_1-A_2} + B_1 \ge A_3\dfrac{B_2-B_1}{A_1-A_2} + B_3\\ \color{red}{\dfrac{B_2-B_1}{A_2-A_1}\ge\dfrac{B_3-B_1}{A_3-A_1}}$$

可以发现这个式子很像斜率

如果记 $P_i(A_i,B_i)$

那么答案就是点集 $\{P_i\}$ 构成的上凸壳

为什么是上凸壳？显然我们选定的是斜率大且尽可能截距大

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
struct vct
{
    double x,y;int id;
    vct operator-(const vct &o)const
    {
        return (vct){x-o.x,y-o.y};
    }
}p[N];
int n,stk[N],top;
double cross(vct a,vct b)
{
    return a.x*b.y-a.y*b.x;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> p[i].x >> p[i].y;
        p[i].id=i;
    }
    sort(p+1,p+1+n,[](vct a,vct b)
    {
        return a.x==b.x?a.y>b.y:a.x>b.x;
    });
    stk[++top]=1;
    for(int i=2; i<=n; i++)
    {
        if(p[i-1].x==p[i].x)continue;
        while(top>1&&cross(p[stk[top]]-p[stk[top-1]],p[i]-p[stk[top]])<=0)
            --top;
        stk[++top]=i;
    }
    sort(stk+1,stk+1+top,[](int a,int b)
    {
        return p[a].id<p[b].id;
    });
    for(int i=1; i<=top; i++)
        cout << p[stk[i]].id << " ";
    return 0;
}