题解 P3194 【[HNOI2008]水平可见直线】

Lskkkno1 · 2020-01-16 08:43:16 · 题解

Luogu

题目描述

给定若干条直线 (都是 y = Ax + B 的形式)

求从上往下看所有可以看到的直线，从小往大输出编号

正解

从上往下看，若干条直线构成的半平面交的部分才是可见的

听说直接做半平面交可以 O(nlogn) 做，但是我不会

由于 -k 和 b 是固定的，所以可以先把它看成一个定点 (-k, b)

对于每一个 x，我们要求最大的 y

把 x 看作是斜率，则 y 就是 y 轴上的截距

发现对于所有的定点 (-k, b) ，只有在(上)凸包的点是有用的

(伪)证明 : 想象一条斜率为 x 的直线从上往下去靠，靠到第一个点时 y 轴截距最大，这个靠到第一个点肯定是凸包上的点

那直接对点集 (-k, b) 求上凸包就完了

我这份代码在 bzoj 上过了，但在 luogu 上过不了，窝佛了

/*
    从上往下看, 若干条直线构成的半平面交的部分是可见的
    y = kx + b
    转化成对偶问题, 求上凸包, 只有凸包上的点才是可见的
    -kx + y = b
    相当于对于不同的 x, 要求最大的 y
*/
#include <bits/stdc++.h>
#define N 50005

using namespace std;

typedef long long LL;

int n;
int stk[N];
bool vis[N];

struct vec {
    LL x, y;
    vec (int _x = 0, int _y = 0) { x = _x, y = _y; }
    vec operator + (const vec &t) const { return vec(x + t.x, y + t.y); }
    vec operator - (const vec &t) const { return vec(x - t.x, y - t.y); }
    bool operator < (const vec &rhs) const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
}a[N];

map<vec, int> id;

inline LL crop(const vec &u, const vec &v) { // 叉积
    return u.x * v.y - v.x * u.y;
}

int main() {
    scanf("%d", &n);
    for(int i = 1, x, y; i <= n; ++i) {
        scanf("%d%d", &x, &y);
        a[i] = vec(-x, y);
        id[a[i]] = i;
    }

    sort(a + 1, a + n + 1, less<vec>());

    int top = 0;
    for(int i = 1; i <= n; ++i) {
        while(top >= 2 && crop(a[i] - a[stk[top - 1]], a[stk[top]] - a[stk[top - 1]]) <= 0)
            --top;
        stk[++top] = i;
    }

    for(int i = 1; i <= top; ++i)
        vis[id[a[stk[i]]]] = true;
    for(int i = 1; i <= n; ++i)
        if(vis[i])
            printf("%d ", i);
    putchar('\n');
    return 0;
}