Description
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号，两两中间用空格隔开.
Sample Input
3
-1 0
1 0
0 0
Sample Output
1 2
YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY
首先处理直线将斜率相同的按B值得大小排序，大的在上，小的在下，只需判断斜率是否相同，如果相同，直接跳过，否则判断交点，stack数组装的是可见直线的id(排序后的)，如果stack的顶部和第二个直线的交点与当前的直线和stack顶部的比横坐标小就装入stack中，否则，stack,弹出栈顶元素；反复操作；
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
double a,b;
int d;
}line[50008];
int cmp(node x,node y)
{
if(x.a==y.a)
return x.b>y.b;
return x.a<y.a;
}
int stack[50008],stack2[50008];
int main()
{
int n,i,j,k,m,d;
scanf("%d",&m);
for(i=0;i<m;i++)
{scanf("%lf%lf",&line[i].a,&line[i].b);
line[i].d=i+1;}
sort(line,line+m,cmp);
stack[0]=0;
i=1;d=1;
while(i<m)
{
if(line[i].a!=line[i-1].a)
break;
i++;
}
stack[d++]=i;
for(;i<m;i++)
{
if(line[i].a==line[stack[d-1]].a)
continue;
double aa=line[i].a,bb=line[i].b;
while(1)
{
if(d==1)
{stack[d++]=i;
break;}
double cc=line[stack[d-1]].a,dd=line[stack[d-1]].b;
double ee=line[stack[d-2]].a,ff=line[stack[d-2]].b;
double x=(dd-bb)/(aa-cc),y=(ff-bb)/(aa-ee);
if(x>y)
{stack[d++]=i;break;}
else
d--;
}
}
for(i=0;i<d;i++)
stack2[i]=line[stack[i]].d;
sort(stack2,stack2+d);
for(i=0;i<d-1;i++)
printf("%d ",stack2[i]);
printf("%d\n",stack2[d-1]);
return 0;
}
