当前位置：首页 > news >正文

[HNOI2008]水平可见直线

news 来源：原创 2024/4/24 2:14:35

看似一个半平面交

但是一般的半平面交用求的是凸包，这个是一个凸壳。封闭区间和半开放区间还是有区别的。

当然一般的半平面交其实可以，只要把向量的方向设对即可（只有1/4象限的向量）

但是既然直接给了斜率的话，而且半开放的区间，还有一个简单一些的做法：

考虑直线按照斜率排序，斜率相同纵截距排序

两个栈，一个维护交点，一个维护直线

加入一个直线，如果和最后一个直线的交点在前一个交点的左方（或者重合），那么这个直线和交点都被盖住了。

不断一起弹栈

画个图就很好理解。

O(nlogn+n)

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=50000+5;
struct po{
    double x,y;
    bool friend operator <(po a,po b){
        if(a.x!=b.x) return a.x<b.x;
        return a.y>=b.y;
    }
}sta[N];
int top1;
int n;
struct line{
    int k,b;
    int id;
    bool friend operator <(line a,line b){
        if(a.k==b.k) return a.b>b.b;
        return a.k<b.k;
    }
}l[N],zhan[N];
int top2;
int ans[N],tot;
po calc(line a,line b){//warning!!! pingxing !!
    po ret;
    ret.x=((double)b.b-(double)a.b)/((double)a.k-(double)b.k);
    ret.y=b.k*ret.x+b.b;
    return ret;
}
int main(){
    rd(n);
    for(reg i=1;i<=n;++i){
        rd(l[i].k);rd(l[i].b);
        l[i].id=i;
    }
    sort(l+1,l+n+1);
    zhan[++top2]=l[1];
    for(reg i=2;i<=n;++i){
        while(i<=n&&l[i].k==l[i-1].k) ++i;
        if(i>n) break;
        while(top1&&calc(l[i],zhan[top2])<sta[top1]){
            --top1;--top2;
        }
        sta[++top1]=calc(l[i],zhan[top2]);
        zhan[++top2]=l[i];
    }
    for(reg i=1;i<=top2;++i){
        ans[++tot]=zhan[i].id;
    }    
    sort(ans+1,ans+tot+1);
    for(reg i=1;i<=tot;++i){
        printf("%d ",ans[i]);
    }
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/12/26 15:19:22
*/