[HNOI2008] [BZOJ1007] 水平可见直线|乱搞

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

 

//省选Round1之前写了俩晚上一直过不了。在Round1之前的那晚突然明白了错在哪了，暴力递归+贪心果然有bug。所以今天直接重新用栈写的。成功AC。

 

分析：

经过分析，我们可以先双关键字将所有直线进行排序。维护一个栈，每次向栈里从小到大加直线，判断栈顶的三条直线，设为l1,l2,l3吧。若l1 l2的交点在l2,l3交点的右边，那么l2就会被彻底覆盖，visit数组赋成false。继续递归。若不会被覆盖，则加进栈中此条边，继续处理下一条边。

对于斜率相同截距不同的直线直接特殊处理就好。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
using namespace std;
struct node
{
    double k,b;
    int num;
};
node q[55555],a[55555];
int n,top;
double x1,x2;
bool visit[55555];
bool cmp(node x,node y)
{
     return x.k<y.k||x.k==y.k&&x.b>y.b;
}
double calc(node x,node y)
{
    return (x.b-y.b)/(y.k-x.k);
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) 
    {
        scanf("%lf%lf",&a[i].k,&a[i].b);
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    memset(visit,1,sizeof(visit));
    top=0;
    for (int i=1;i<=n;i++)
    {
        if (top==0)
        {
            q[++top]=a[i];
            continue;
        }
        if (q[top].k==a[i].k) 
        {
            visit[a[i].num]=false;
            continue;
        }
        if (top==1)
        {
            q[++top]=a[i];
            continue;
        }
        while (1)
        {
            if (top==1) 
            {
                q[++top]=a[i];
                break;
            }
            x1=calc(q[top],a[i]);
            x2=calc(q[top-1],q[top]);
            if (x1<=x2)
            {
                visit[q[top].num]=false;
                top--;
            }
            else 
            {
                 q[++top]=a[i];
                 break;
            }
        }
    }
    for (int i=1;i<=n;i++) if (visit[i]) printf("%d ",i);
    return 0;
}