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

2024-01-31 21:03:46

1007: [HNOI2008]水平可见直线

Description

在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

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

Sample Input

3
-1 0
1 0
0 0

Sample Output

1 2

HINT

题解：

当前直线与相对他斜率次大和次次大的2条直线时，如果与次大的（或者次次大）的交点在次大与次次大的交点左边，那么次大的直线一定被覆盖掉了！

画图自己看！（其实也就是这三个点形成一个凸包，然后上凸包的边所在直线一定看得到，下凸包一定被覆盖！）

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+, M = , mod = 1e9 + , inf = 0x3f3f3f3f;

typedef long long ll;

#define eps 1e-8

struct line{double a,b;int index;}l[N],seg[N];

bool bo[N];

int top = , n ;

int cmp (line x,line y) {

    if(fabs(x.a-y.a)<=eps) return x.b<y.b;

    return x.a<y.a;

}

double crossx(line x,line y) {

     return (y.b-x.b) / (x.a-y.a);

}

void inserts(line x) {

    while(top) {

        if(fabs(seg[top].a - x.a)<=eps) top--;

        else if(top>&&crossx(x,seg[top-])<=crossx(seg[top],seg[top-]))

            top--;

        else break;

    }

    seg[++top] = x;

}

void solve() {

    sort(l+,l+n+,cmp);

    for(int i=;i<=n;i++) inserts(l[i]);

    for(int i=;i<=top;i++) bo[seg[i].index] = true;

    for(int i=;i<=n;i++)

        if(bo[i]) printf("%d ",i);

    printf("\n");

}

int main() {

    scanf("%d",&n);

    for(int i=;i<=n;i++) {

        scanf("%lf%lf",&l[i].a,&l[i].b);

        l[i].index = i;

    }

    solve();

}

码农公寓