记录编号	251390	评测结果	AAAAAAAAAA
题目名称	1831.[HNOI 2008]水平可见直线	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2016-04-17 19:33:01	内存使用	12.21 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>

const double eps=1e-10;

int n;
struct u
{
	int id;
	double K;
	double B;
}c[500010];
bool b[500010];
int st[500010],tp;

inline bool gK(const u & aa,const u & bb)
{
	if(fabs(aa.K-bb.K)<eps)
	    return aa.B>bb.B;
	return aa.K<bb.K;
}

inline double gjd(int a,int b)
{
	return (c[b].B-c[a].B)/(c[a].K-c[b].K);
}

int main()
{
	freopen("bzoj_1007.in","r",stdin);
	freopen("bzoj_1007.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	    scanf("%lf%lf",&c[i].K,&c[i].B);
	    c[i].id=i;
	}
	std::sort(c+1,c+1+n,gK);
	int l=0;
	c[0].K=500001.0;
	for(int i=1;i<=n;i++)
	    if(fabs(c[i].K-c[i-1].K)>eps)
	        c[++l]=c[i];
	st[++tp]=1;
	st[++tp]=2;
	//printf("%d %d %d\n",c[1].id,c[2].id,c[3].id);
	for(int i=3;i<=l;i++)
	{
		//printf()
		while(tp>=2&&gjd(i,st[tp])<gjd(st[tp],st[tp-1])+eps)
		    --tp;
		st[++tp]=i;
	}
	for(int i=1;i<=tp;++i)
	    b[c[st[i]].id]=1;
	for(int i=1;i<=n;++i)
	    if(b[i])
	        printf("%d ",i);
	getchar();
	getchar();
}