记录编号	420488	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]水平可见直线	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2017-07-04 21:40:56	内存使用	1.63 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=50010;
struct line{
	int id,k,b;
	line(int ID=0,int K=0,int B=0){
		id=ID;k=K;b=B;
	}
	line operator - (const line &x)const{return line(0,k-x.k,b-x.b);}
	ll operator * (const line &x)const{return (ll)k*x.b-(ll)b*x.k;}
}l[N],q[N];
bool cmp(const line &x,const line &y){
	return x.k==y.k?x.b>y.b:x.k<y.k;
}
bool check(line x,line y,line z){
	return (y-x)*(z-x)>=0;
}
int n,tail,a[N];
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("%d%d",&l[i].k,&l[i].b),l[i].id=i;
	sort(l+1,l+n+1,cmp);
	l[0].k=-1e9;
	tail=0;
	for (int i=1;i<=n;i++)
	if (l[i].k!=l[i-1].k){
		for (;1<tail&&check(q[tail-1],q[tail],l[i]);tail--);
		q[++tail]=l[i];
	}
	int cnt=0;
	for (int i=1;i<=tail;i++) a[++cnt]=q[i].id;
	sort(a+1,a+cnt+1);
	for (int i=1;i<=cnt;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}