记录编号	371656	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2017-02-16 16:25:10	内存使用	42.27 MiB

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
const double INF=1E30;
const double EPS=1E-10;
int dcmp(const double&p) {
	return fabs(p)<EPS?0:p<0?-1:1;
}
typedef struct Point {
	double x,y;
	Point():x(0),y(0) {}
	Point(double X,double Y):x(X),y(Y){}
}Vector;
typedef const Vector& CVector,CPoint;
inline Vector operator + (CVector a,CVector b) {
	return Vector(a.x+b.x,a.y+b.y);
}
inline Vector operator - (CVector a,CVector b) {
	return Vector(a.x-b.x,a.y-b.y);
}
inline Vector operator * (CVector a,const double&b) {
	return Vector(a.x*b,a.y*b);
}
inline double Cross(CPoint a,CPoint b) {
	return a.x*b.y-a.y*b.x;
}
struct Line {
	Point p;Vector v;double ang;int seq;
	Line(){ang=0.0;seq=-1;}
	Line(CPoint P,CVector V,int SEQ=-1):p(P),v(V),seq(SEQ){ang=atan2(v.y,v.x);}
};
typedef const Line& CLine;
inline bool operator < (CLine a,CLine b) {
	return a.ang<b.ang;
}
inline bool SeqCmperInLine(CLine a,CLine b) {
	return a.seq<b.seq;
}
inline bool OnLeft(CLine l,CPoint p) {
	return Cross(l.v,p-l.p)>0;
}
inline Point GetIntersection(CLine a,CLine 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) {
	std::sort(L,L+N);
	int first,last;
	Point *p=new Point[N];
	Line *q=new Line[N];
	q[first=last]=L[0];
	for(int i=1;i<N;++i) {
		while(first<last&&!OnLeft(L[i],p[last-1]))last--;
		while(first<last&&!OnLeft(L[i],p[first] ))first++;
		q[++last]=L[i];
		if(dcmp(Cross(q[last].v,q[last-1].v))==0) {
			last--;
			if(OnLeft(q[last],L[i].p))q[last]=L[i];
		}
		if(first<last)p[last-1]=GetIntersection(q[last-1],q[last]);
	}
	while(first<last&&!OnLeft(q[first],p[last-1]))last--;
	if(last-first<=1)return 0;
	p[last]=GetIntersection(q[last],q[first]);

	int m=0;
	for(int i=first;i<=last;++i)poly[m++]=q[i];
	return m;
}
const int MAXN=5E5+10;
Line w[MAXN],c[MAXN];
int main() {
	freopen("bzoj_1007.in","r",stdin);
	freopen("bzoj_1007.out","w",stdout);
	int N,m=0;
	scanf("%d",&N);
	for(int i=0;i<N;++i) {
		double a,b;
		scanf("%lf%lf",&a,&b);
		w[m++]=Line(Point(0,b),Vector(1,a),i);
	}
	w[m++]=Line(Point(0,-INF),Vector(+1,0));
	w[m++]=Line(Point(+INF,0),Vector(0,+1));
	w[m++]=Line(Point(0,+INF),Vector(-1,0));
	w[m++]=Line(Point(-INF,0),Vector(0,-1));
	m=HalfPlaneIntersection(w,m,c);
	std::sort(c,c+m,SeqCmperInLine);
	for(int i=0;i<m;++i) {
		if(c[i].seq==-1)continue;
		else printf("%d ",c[i].seq+1);
	}
	return 0;
}