记录编号	375091	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2017-02-24 17:55:26	内存使用	5.14 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e15
#define eps 1e-8
const int maxn=55000;
struct Point{
	double x,y;
	Point(double xx=0,double yy=0){x=xx;y=yy;}
};
typedef Point Vector;

Vector operator - (Point A,Point B)
{return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double x)
{return Vector(A.x*x,A.y*x);}

Point operator + (Point A,Vector B)
{return Point(A.x+B.x,A.y+B.y);}

double Cross(Vector A,Vector B)
{return A.x*B.y-A.y*B.x;}

int dcmp(double x)
{return fabs(x)<eps ? 0 : x>0 ? 1 : -1;}

struct Line{
	Point P;Vector v;
	double ang;int id;
	Line(){};
	Line(Point A,Vector B,int ID=0){
		P=A;v=B;id=ID;
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line & a)const{
		return ang<a.ang;
	}
};

bool OnLeft(Line L,Point P)
{return dcmp(Cross(L.v,P-L.P))>0;}

Point LineInterSection(Line A,Line B){
	Vector u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}

int HalfPlaneInterSection(Line *L,int n,Line *poly){
	sort(L,L+n);
	Point *p=new Point[n];
	Line *q=new Line[n];
	int head,tail;
	q[head=tail=0]=L[0];
	for(int i=1;i<n;i++){
		while(head<tail && !OnLeft(L[i],p[tail-1]))tail--;
		while(head<tail && !OnLeft(L[i],p[head  ]))head++;
		q[++tail]=L[i];
		if(dcmp(Cross(q[tail].v,q[tail-1].v))==0){
			tail--;
			if(head<tail && OnLeft(q[tail],L[i].P))q[tail]=L[i];
		}
		if(head<tail)p[tail-1]=LineInterSection(q[tail-1],q[tail]);
	}
	while(head<tail && !OnLeft(q[head],p[tail-1]))tail--;
	if(tail-head<=1)return 0;
	p[tail]=LineInterSection(q[head],q[tail]);
	int m=0;
	for(int i=head;i<=tail;i++)poly[m++]=q[i];
	return m;
}
int n,cnt,Ans[maxn];
Line L[maxn],poly[maxn];
void Init();
int main(){
	freopen("bzoj_1007.in","r",stdin);
	freopen("bzoj_1007.out","w",stdout);
    Init();
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		double A,B;scanf("%lf%lf",&A,&B);
		L[cnt++]=Line(Point(0,B),Vector(1,A),i);
	}
	L[cnt++]=Line(Point(Inf,0),Vector(0,1));
	L[cnt++]=Line(Point(0,Inf),Vector(-1,0));
	L[cnt++]=Line(Point(-Inf,0),Vector(0,-1));
	L[cnt++]=Line(Point(0,-Inf),Vector(1,0));
	int m=HalfPlaneInterSection(L,cnt,poly);
	m--;
	for(int i=0;i<m;i++)Ans[i]=poly[i].id;
	sort(Ans,Ans+m);
	for(int i=0;i<m;i++)printf("%d ",Ans[i]);
}