[BZOJ 1007] [HNOI2008] 水平可见直线

Posted on | In , | Views:

题目链接

BZOJ 1007

做法

我们每加入一条直线，那么它下方的直线就看不到了。所以最后能看到的形状一定是一个下凸壳。
所以我们先按斜率从小到大排序。
用一个单调栈维护每一段凸壳是哪一条直线，以及这一段凸壳的左端点。
每次加入一条新的直线，如果这条直线与目前栈顶的这条直线的交点，小于这段凸壳的左端点，那么栈顶这条直线一定不在凸壳上了，从栈中弹出。
最后加入我这条直线就行了。
至于精度问题，博主在算交点的时候，用两个整数来表示这个交点的分子和分母，存的时候也存两个整数，就能解决了。

代码

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
55
56
57
58
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,top,t;
int st[N],dk[N],db[N],ans[N]; 
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
struct node{
    int k,b,id;
}a[N];
inline bool cmp(node a,node b){
    return a.k==b.k?a.b>b.b:a.k<b.k;
}
int main(){
    read(n);
    for (int i=1;i<=n;i++){
        read(a[i].k),read(a[i].b);
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    st[++top]=1;
    for (int i=2;i<=n;i++){
        if (a[i].k==a[i-1].k) continue;
        int tk=a[i].k-a[st[top]].k,tb=a[st[top]].b-a[i].b;
        //printf("%d %d\n",tk,tb);
        while (top&&1ll*tb*dk[top]<=1ll*db[top]*tk&&st[top]!=1){
            top--;
            tk=a[i].k-a[st[top]].k,tb=a[st[top]].b-a[i].b;
        }
        st[++top]=i;
        db[top]=tb;
        dk[top]=tk;
    }
    while (top){
        ans[++t]=a[st[top]].id;
        top--;
    }
    sort(ans+1,ans+t+1);
    for (int i=1;i<=t;i++) printf("%d ",ans[i]);
    return 0;
}