BZOJ 1007 水平可见直线

时间:2019-12-13 09:50:55   收藏:0   阅读:87

题面

题意

??以点斜式给出 \(n\) 条直线,求从 \(y=+\infty\) 处往下看,哪些直线是可见的。

题解

??按斜率升序排序,相同斜率保留最高的,之后用栈来维护可见的直线。

??每次加入新直线时,如果栈顶的两条直线交点不高于直线,说明栈顶的直线已经被新直线和上一条直线完全覆盖,弹出栈顶的直线。


代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e4+5;
struct line{
    ll a,b,id;
    line operator = (const line &l){
        a=l.a; b=l.b; id=l.id;
    }
};
inline bool cmp(const line &a,const line &b){
    if (a.a!=b.a) return a.a<b.a;
    if (a.b!=b.b) return a.b>b.b;
    return false;
}
inline bool eaq(const line &a,const line &b){
    return a.a==b.a;
}
inline bool check(const line &a,const line &b,const line &c){
    return (a.b-b.b)*a.a+a.b*(b.a-a.a)<=(a.b-b.b)*c.a+c.b*(b.a-a.a);
}
line a[maxn];
int id[maxn];
int main(){
    int i,n,m;
    scanf("%d",&n);
    for (i=0;i<n;i++){
        scanf("%lld%lld",&a[i].a,&a[i].b);
        a[i].id=i+1;
    }
    sort(a,a+n,cmp); n=unique(a,a+n,eaq)-a;
    m=0;
    for (i=0;i<n;i++){
        while (m>1&&check(a[m-2],a[m-1],a[i]))
            m--;
        a[m++]=a[i];
    }
    for (i=0;i<m;i++) id[i]=a[i].id;
    sort(id,id+m);
    for (i=0;i<m;i++) printf("%d ",id[i]);
    return 0;
}

原文:https://www.cnblogs.com/Kilo-5723/p/12033375.html

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!