记录编号	375095	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013] 赛车	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2017-02-24 18:30:45	内存使用	1.95 MiB

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <vector>
#define Mem(a,v) memset(a,v,sizeof a)
#define Mcpy(a,b) memcpy(a,b,sizeof a)
using namespace std;
typedef long long LL;
const double inf = 1e30;
const double eps = 1e-16;
const int maxn = 10010;
int dcmp(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
struct Point
{
	double x,y;
	Point(double x=0,double y=0): x(x), y(y){}
	Point(Point a,Point b){ x=b.x-a.x, y=b.y-a.y; }
};
typedef Point Vector;
struct Line
{
	Point p; Vector v; double ang; int id;
	Line(){}
	Line(Point p,Vector v,int id): p(p),v(v),id(id){ ang=atan2(v.y,v.x); }
	bool operator < (const Line &b)const{
		if(dcmp(ang-b.ang)==0) return p.y<b.p.y;
		else return ang<b.ang;
	} 
};
double operator * (Vector a,Vector b)
{ return a.x*b.y - a.y*b.x; }
Vector operator + (Vector a,Vector b)
{ return Vector(a.x+b.x, a.y+b.y); }
Vector operator * (Vector a,double p)
{ return Vector(a.x*p, a.y*p); }
bool OnLeft(Line a,Point b)
{ return dcmp(a.v*Vector(a.p,b))>=0; }
Point GetIntersection(Line a,Line b){
	Vector u = Vector(b.p, a.p);
	double t = (b.v*u)/(a.v*b.v);
	return a.p+a.v*t;
}

Line q[maxn];
Point p[maxn];
int HalfPlaneIntersection(Line *a,int n,Line *poly){
	int first,last;
	q[first=last=0] = a[1];
	for(int i = 2; i <= n; i ++ ){
		while(first<last && !OnLeft(a[i],p[last-1])) last--;
		while(first<last && !OnLeft(a[i],p[first])) first++;
		q[++last] = a[i];
		if(dcmp(q[last].v*q[last-1].v)==0){
			last--;
			if(OnLeft(q[last],a[i].p)) q[last]=a[i];
		} 
		if(first<last) p[last-1] = GetIntersection(q[last],q[last-1]);
 	}
 	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; 
}
bool CmpLineId(const Line &A,const Line &B){ return A.id < B.id; }
int n,m;
double B[maxn];
Line a[maxn],c[maxn];
vector <int> G[maxn];
int ans[maxn];
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("race1.in","r",stdin);
	freopen("race1.out","w",stdout);
#endif
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++ ) scanf("%lf", &B[i]);
	for(int i = 1; i <= n; i ++ ){
		double A; scanf("%lf", &A);
		a[++m] = Line(Point(0,B[i]),Vector(1,A),i);
	}
	a[++m] = Line(Point(0,0),Vector(0,-1),-1);
	a[++m] = Line(Point(-inf,0),Vector(0,-1),-1);
	a[++m] = Line(Point(0,-inf),Vector(1,0),-1);
	a[++m] = Line(Point(inf,0),Vector(0,1),-1);
	a[++m] = Line(Point(0,inf),Vector(-1,0),-1);

	sort(a+1, a+1+m);
	int pa = 0;
	for(int i = 1; i <= m; i ++ ){
		if(a[i].id == -1) continue;
		if(dcmp(a[i].ang-a[i-1].ang)==0 && dcmp(a[i].p.y-a[i-1].p.y)==0){
			G[pa].push_back(a[i].id);
			a[i] = Line(Point(0,0),Vector(0,-1),-1);
		} else pa = a[i].id;
	}


	m = HalfPlaneIntersection(a, m, c);

	sort(c+1, c+1+m, CmpLineId);

	int str = 1;
	for(int i = 1; i <= m; i ++ ){
		if(c[i].id > 0){ str = i; break; }
	}
	int num = 0;
	for(int i = str; i <= m; i ++ ){
		int pos = c[i].id;
		ans[++num] = pos;
		int sz = G[pos].size();
		if(sz){
			for(int j = 0; j < sz; j ++ ){
				ans[++num] = G[pos][j];
			}
		}
	}

	printf("%d\n", num);
	sort(ans+1, ans+1+num);

	for(int i = 1; i <= num; i ++ )
		printf("%d ", ans[i]);

	return 0;
}