记录编号	255117	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.488 s
提交时间	2016-04-26 21:41:40	内存使用	2.72 MiB

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define eps 0
#define inf 1e15
bool flag[50010];
int n,l,r;
struct point{double x,y;};
struct line{point a,b;int id;double ang;}o[50010],q[50010];
inline point operator - (const point &a,const point &b){
	return (point){b.x-a.x,b.y-a.y};
}
inline double operator * (const point &a,const point &b){
	return a.x*b.y-a.y*b.x;
}
inline point inter(const line &a,const line &b){
	double k1,k2,t;
	k1=(b.b-a.a)*(a.b-a.a);
	k2=(a.b-a.a)*(b.a-a.a);
	t=k1/(k1+k2);
	return (point){b.b.x+(b.a.x-b.b.x)*t,b.b.y+(b.a.y-b.b.y)*t};
}
inline bool operator < (const line &a,const line &b){
	return a.ang==b.ang?(a.b-a.a)*(b.b-a.a)>0:a.ang<b.ang;
}
inline bool judge(const line &a,const line &b,const line &t){
	return (t.b-t.a)*(inter(a,b)-t.a)<eps;
}
bool work(){
	freopen("bzoj_1007.in","r",stdin);
	freopen("bzoj_1007.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,k,b;i<=n;++i)
	    scanf("%d%d",&k,&b),
	    o[i].a=(point){0,b},
	    o[i].b=(point){1,k+b},
		o[i].id=i;
	o[++n].a=(point){inf,0},o[n].b=(point){inf,1};
	o[++n].a=(point){inf,inf},o[n].b=(point){inf-1,inf};
	o[++n].a=(point){-inf,inf},o[n].b=(point){-inf,inf-1};
	for(int i=1;i<=n;++i)
	    o[i].ang=atan2(o[i].b.y-o[i].a.y,o[i].b.x-o[i].a.x);
	std::sort(o+1,o+n+1);
	int tot=n;o[n=1]=o[1];
	for(int i=2;i<=tot;o[n]=o[i],++i)
	    if(fabs(o[i].ang-o[i-1].ang)>eps)++n;
	q[l=0]=o[1],q[r=1]=o[2];
	for(int i=3;i<=n;++i){
		while(l<r&&judge(q[r-1],q[r],o[i]))--r;
		while(l<r&&judge(q[l+1],q[l],o[i]))++l;
		q[++r]=o[i];
	}
	while(l<r&&judge(q[l+1],q[l],q[r]))++l;
	for(int i=l;i<=r;++i)
	    flag[q[i].id]=1;
	for(int i=1;i<=tot;++i)
	    if(flag[i])printf("%d ",i);
	//while(1);
}
bool tt=work();
main(){;}