Bzoj1007 水平可见直线

 

 

Time Limit: 1000MS

Memory Limit: 165888KB

64bit IO Format: %lld & %llu

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

Hint

Source

HNOI2008

 

比较好思考的几何问题。

先把所有的直线按斜率从小到大排序，然后一个一个添加：如果目前枚举到的这条直线与上一次添加的直线的交点“在上一个交点的左边”，那么添加这条也没用，继续枚举下一条；否则就添加这一条。

↑可以用单调栈来维护。

操作完后用桶排序的方法存一下可见直线的编号，然后按顺序输出。

 

/**/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int mxn=100000;
const double eps=1e-8;
int st[mxn],top;
bool flag[mxn];
struct line{
    double k,b;
    int mk;
}a[mxn];
int n;
int cmp(const line x,const line y){//按照斜率排序 
    if(fabs(x.k-y.k)<eps)return x.b<y.b;
    return x.k<y.k;
}
double csx(int i,int j){
    return (double)(a[j].b-a[i].b)/((double)(a[i].k-a[j].k));
} 
int main(){
    scanf("%d",&n);
    if(n==1){printf("1 ");return 0;}
    int i,j;
    for(i=1;i<=n;i++)scanf("%lf%lf",&a[i].k,&a[i].b),a[i].mk=i;
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;i++){
        while(top){
            if(fabs(a[st[top]].k-a[i].k)<eps)top--;
            if(top>1 && csx(i,st[top-1])<=csx(st[top],st[top-1]))top--;
            else break;
        }
        st[++top]=i;
    }
    for(i=1;i<=top;i++)flag[a[st[i]].mk]=1;//标记序号以便按顺序输出 
    for(i=1;i<=n;i++)if(flag[i])printf("%d ",i);
    return 0;
}