【bzoj1007】[HNOI2008]水平可见直线

2015.04.16 15:57 Thu | 28次阅读 | 旧日oi | 固定链接 | 源码

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

题解

JLOI2013年赛车的翻版……
按斜率从小到大排序,判断一下斜率相同的,保留最上边一条。然后依次入栈,如果栈顶和当前要入栈直线的交点在栈顶和栈顶下面那条直线的交点的左边,说明这条直线永远不会被看到,弹栈就行。
本来以为要调一会,结果很快就过了……

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 50005
using namespace std;
struct Line{
    double k,b;
    int idx;
}line[maxn],st[maxn];
int n,ans[maxn];
bool cmp(const Line &a,const Line &b)
{
    return a.k<b.k||(a.k==b.k&&a.b>b.b);
}
bool check(Line &a,Line &b,Line &c)
{
    return (a.b-b.b)/(b.k-a.k)>=(a.b-c.b)/(c.k-a.k);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    scanf("%lf%lf",&line[i].k,&line[i].b),line[i].idx=i;
    sort(line+1,line+n+1,cmp);
    int top=1;
    for(int i=2;i<=n;i++)
    {
        if(line[i].k==line[i-1].k) continue;
        line[++top]=line[i];
    }
    n=top;top=2;
    st[1]=line[1];st[2]=line[2];
    ans[1]=line[1].idx;ans[2]=line[2].idx;
    for(int i=3;i<=n;i++)
    {
        while(top>=2&&check(st[top-1],st[top],line[i])) top--;
        st[++top]=line[i];ans[top]=line[i].idx;
    }
    sort(ans+1,ans+top+1);
    for(int i=1;i<=top;i++) printf("%d ",ans[i]);
}```