# Bzoj1007 [hnoi2008]水平可见直线

Posted by yjjr's blog on February 6, 2018

Description

在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为

L1:y=x; L2:y=-x; L3:y=0

Input

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

Output

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

Sample Input

3

-1 0

1 0

0 0

Sample Output

1 2

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
#define eps 1e-8
using namespace std;
const int maxn=5e4+6;
struct node{double x,y;int id;}a[maxn],st[maxn];
int top,n;
bool ans[maxn];
inline bool cmp(node a,node b){return fabs(a.x-b.x)<eps ? a.y<b.y : a.x<b.x;}

double crossx(node a,node b){return (b.y-a.y)/(a.x-b.x);}

void ins(node a)
{
while(top){
if(fabs(st[top].x-a.x)<eps)top--;
else if(top>1&&crossx(a,st[top-1])<=crossx(st[top],st[top-1]))top--;
else break;
}
st[++top]=a;
}

int main()
{
scanf("%d",&n);
rep(i,1,n)scanf("%lf%lf",&a[i].x,&a[i].y),a[i].id=i;
sort(a+1,a+1+n,cmp);
rep(i,1,n)ins(a[i]);
rep(i,1,top)ans[st[i].id]=1;
rep(i,1,n)
if(ans[i])printf("%d ",i);
return 0;
}