1007: [HNOI2008]水平可见直线

Input

第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi

Output

从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格

Sample Input3
-1 0
1 0
0 0

Sample Output1 2

按斜率排序，从小到大插入。半平面交的特殊情况：每次都要保证x坐标<x,top>><top,top'> 否则top不可见（top为栈顶元素）

#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<functional>#include<iostream>using namespace std;#define MAXN (50000+10)int n;struct line{int k,b,i;friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;}friend double intx(line a,line b){return (double)(b.b-a.b)/(a.k-b.k);}}a[MAXN];int s[MAXN],size=0;void push(int x){while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;s[++size]=x;}bool b[MAXN];int main(){scanf("%d",&n);for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}sort(a+1,a+1+n);push(1);for (int i=2;i<=n;i++)if (a[i].k>a[i-1].k) push(i);//for (int i=1;)memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';return 0;}