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

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

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

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

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

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

那么交点的坐标是什么呢？
A 1 x + B 1 = A 2 x + B 2 x = B 2 − B 1 A 1 − A 2 A_1x+B_1=A_2x+B_2\ x=dfrac{B_2-B_1}{A_1-A_2} A1​x+B1​=A2​x+B2​x=A1​−A2​B2​−B1​​
则
A 1 B 2 − B 1 A 1 − A 2 + B 1 ≥ A 3 B 2 − B 1 A 1 − A 2 + B 3 B 2 − B 1 A 2 − A 1 ≥ B 3 − B 1 A 3 − A 1 A_1dfrac{B_2-B_1}{A_1-A_2} + B_1 ge A_3dfrac{B_2-B_1}{A_1-A_2} + B_3\ color{red}dfrac{B_2-B_1}{A_2-A_1}gedfrac{B_3-B_1}{A_3-A_1} A1​A1​−A2​B2​−B1​​+B1​≥A3​A1​−A2​B2​−B1​​+B3​A2​−A1​B2​−B1​​≥A3​−A1​B3​−B1​​
可以发现这个式子很像斜率

如果记 P i ( A i , B i ) P_i(A_i,B_i) Pi​(Ai​,Bi​)

那么答案就是点集 { P i } {P_i} {Pi​} 构成的上凸壳

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

代码如下

#include 
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 
转载请说明出处