bzoj 1007

[HNOI2008]水平可见直线

Description

在 $xOy$ 直角坐标平面上有 $n$ 条直线 $L_1, L_2, \dots, 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$ 条直线两两不重合. 求出所有可见的直线.

Input

第一行为 $N(0 < N < 50000)$ , 接下来的 $N$ 行输入 $A_i, B_i$ .

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input

Sample Output

1 2

题解

一个显然的观察是当两条直线斜率相同时，截距小的直线一定被截距大的直线覆盖，故只考虑每个不同的斜率中截距最大的直线.

经过观察，从左往右可见的直线的斜率是增加的，可以维护一个单调栈，按照斜率从小到大的顺序遍历所有直线，如果此时栈内元素不少于两个，就比较栈顶是否被当前直线和栈顶前一个直线覆盖，如果覆盖则弹出栈顶，直到栈内元素少于两个或栈顶不被上述两条直线覆盖，然后把当前直线加入栈顶.

最后栈中的元素就是可见的直线.

吐槽一下，数据范围是错的，有些数据超过了数据范围.

代码

#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long int ll;

#define maxn 50000
#define maxa 500000

int n;
int b[(maxa + 10) << 1];
int id[(maxa + 10) << 1];
int ans[maxn + 10];

bool under(int p, int i, int j)
{
    ll ki = i - maxa, kj = j - maxa, kp = p - maxa;
    ll left = ki * b[j] - kj * b[i];
    ll rig1 = kp * (b[j] - b[i]);
    ll rig2 = 1ll * b[p] * (ki - kj);
    return left >= (rig1 + rig2);
}

int top;
int stk[maxn + 10];

int main(void)
{
    int i;
    for (i = 0; i <= (maxa << 1); i++) b[i] = - maxa - 1;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        int ai, bi;
        scanf("%d%d", &ai, &bi);
        if (bi > b[maxa + ai])
        {
            b[maxa + ai] = bi;
            id[maxa + ai] = i + 1;
        }
    }
    for (i = 0; i <= (maxa << 1); i++)
        if (b[i] >= (-maxa))
        {
            while ((top > 1) && under(stk[top - 1], i, stk[top - 2])) top--;
            stk[top++] = i;
        }
    for (i = 0; i < top; i++) ans[id[stk[i]]] = 1;
    for (i = 1; i <= n; i++)
        if (ans[i]) printf("%d ", i);
    puts("");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

# bzoj 1007

# [HNOI2008]水平可见直线

# Description

# Input

# Output

# Sample Input

# Sample Output

# 题解

# 代码