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
-1 0
1 0
0 0
Sample Output
1 2
这道题按斜率排序后维护一个单点序列，怎么写怎么对。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=;
struct Node{
int k,b,id;
friend bool operator<(Node a,Node b){
if(a.k!=b.k)return a.k<b.k;
return a.b>b.b;
}
}l[N]; double Cx(Node a,Node b){
return 1.0*(a.b-b.b)/(b.k-a.k);
} int n,m;
int st[N],top;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%d",&l[i].k,&l[i].b);
l[i].id=i;
}
sort(l+,l+n+);
for(int i=;i<=n;i++){
if(l[i].k!=l[i-].k)
l[++m]=l[i];
}
n=m;
st[top=]=;
for(int i=;i<=n;i++){
while(top>&&Cx(l[i],l[st[top]])<=Cx(l[st[top]],l[st[top-]]))top-=;
st[++top]=i;
}
for(int i=;i<=top;i++)
st[i]=l[st[i]].id;
sort(st+,st+top+);
for(int i=;i<=top;i++)
printf("%d ",st[i]);
return ;
}