记录编号	372213	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013] 赛车	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2017-02-17 21:22:19	内存使用	4.49 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef double db;
struct pt{
	db x,y;int id;
	pt(db X=0,db Y=0,int ID=0){x=X;y=Y;id=ID;}
	pt operator + (const pt a)const{return pt(x+a.x,y+a.y,0);}
	pt operator - (const pt a)const{return pt(x-a.x,y-a.y,0);}
	db operator ^ (const pt a)const{return x*a.y-y*a.x;}
	bool operator == (const pt a)const{return x==a.x&&y==a.y;}
	bool operator < (const pt a)const{return x==a.x?y>a.y:x<a.x;}
}p[N],q[N];
int n,a[N],size;
db check(pt x,pt y,pt z){//判定x和y的交点是否在z下面 
	return (y-x)^(z-x);
}
int main()
{
	freopen("race1.in","r",stdin);
	freopen("race1.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf",&p[i].y),p[i].id=i;
	for (int i=1;i<=n;i++) scanf("%lf",&p[i].x);
	p[++n]=pt(-1e18,0,0);
	sort(p+1,p+n+1);
	int tail=0;
	for (int i=1;i<=n;i++)
	if (p[i].x!=p[i-1].x||p[i]==p[i-1]){
		for (;1<tail&&check(q[tail-1],q[tail],p[i])>0;tail--);
		q[++tail]=p[i];
	}
	printf("%d\n",tail-1);
	for (int i=2;i<=tail;i++) a[++size]=q[i].id;
	sort(a+1,a+size+1);
	for (int i=1;i<=size;i++) printf("%d ",a[i]);
	puts("");
	return 0;
}