M_sea

洛谷3194 [HNOI2008]水平可见直线
LuoguBZOJ分析首先,斜率相同的两条直线,纵截距大的在上面。所以先按斜率从小到大排序,对于斜率相同的只保留纵...
扫描右侧二维码阅读全文
08
2019/01

洛谷3194 [HNOI2008]水平可见直线

Luogu

BZOJ

分析

首先,斜率相同的两条直线,纵截距大的在上面。

所以先按斜率从小到大排序,对于斜率相同的只保留纵截距最大的。

然后,维护一个单调栈,斜率单调递增。

考虑一条新的直线满足什么条件才能覆盖掉栈顶。经过一番分析后发现,如果新的直线与$s[top-1]$的交点在$s[top]$的右边,那么$s[top]$会被覆盖掉。这里的$s$是栈。

注意,一开始要把斜率最小的直线放进来。

然后这题就做完啦。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=50000+10;
const int INF=2e9;

struct Line { int k,b,id; };
Line l[MAXN];
int n,tot=0;
int sta[MAXN],top=0;
int ans[MAXN];

inline int cmp(const Line x,const Line y) {
    return (x.k<y.k)||(x.k==y.k&&x.b>y.b);
}

inline double get(int i,int j) { //求交点的横坐标
    return 1.0*(l[j].b-l[i].b)/(l[i].k-l[j].k);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        l[i].k=read(),l[i].b=read(),l[i].id=i;
    sort(l+1,l+n+1,cmp);
    l[0].k=-INF;
    for (re int i=1;i<=n;++i)
        if (l[i].k!=l[i-1].k) l[++tot]=l[i];
    n=tot;
    
    sta[++top]=1,ans[top]=l[1].id;
    for (re int i=2;i<=n;++i) {
        while (top>1&&get(i,sta[top])<=get(i,sta[top-1])) --top;
        sta[++top]=i,ans[top]=l[i].id;
    }
    
    sort(ans+1,ans+top+1);
    for (re int i=1;i<=top;++i) printf("%d ",ans[i]);
    putchar('\n');
    return 0;
}
最后修改:2019 年 05 月 26 日 05 : 43 PM

2 条评论

  1. smy

    这不是半平面交吗

    1. M_sea
      @smy

      不会半平面交qwq

发表评论