记录编号	158828	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013] 赛车	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2015-04-18 06:04:58	内存使用	0.96 MiB

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

using namespace std;

#define maxn 10010
#define INF 1e15
#define eps 1e-5

struct Point{
	double x, y;
	Point(double x = 0, double y = 0): x(x), y(y) {}
}poly[maxn];

#define Vector Point

Vector operator - (Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator + (Point A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator * (Vector A, double p) { return Vector(p * A.x, p * A.y); }

int dcmp(double x) {
	if(fabs(x) < eps) return 0;
	return x > 0 ? 1: -1;
}

bool operator == (const Point& a, Point& b) {
	return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
} 

struct Line {
	Point P;
	Vector v;
	double ang;
	int pos;
	bool operator < (const Line& L) const {
		return ang < L.ang;
	}
}f[maxn];

int q[maxn], ans[maxn], first, last;

double Cross(Vector A, Vector B) {
	return A.x * B.y - A.y * B.x;
}

bool OnLeft(Line L, Point P) {
	return Cross(L.v, P - L.P) > 0;
}

Point GetIntersection(Line a, Line b) {
	Vector u = a.P - b.P;
	double t = Cross(b.v, u) / Cross(a.v, b.v);
	return a.P + a.v * t;
}

void HalfplaneIntersection(int n) {
	for(int i = 1; i <= n; i++)
		f[i].ang = atan2(f[i].v.y, f[i].v.x);
	sort(f + 1, f + n + 1);
	q[first = last = 1] = 1;
	for(int i = 2; i <= n; i++) {
		while(first < last && !OnLeft(f[i], poly[last - 1])) last--;
		while(first < last && !OnLeft(f[i], poly[first])) first++;
		q[++last] = i;
		if(fabs(Cross(f[q[last]].v, f[q[last - 1]].v)) < eps) {
			last--;
			if(OnLeft(f[q[last]], f[i].P)) q[last] = i;
		}
		if(first < last) poly[last - 1] = GetIntersection(f[q[last - 1]], f[q[last]]);
	}
	while(first < last && !OnLeft(f[q[first]], poly[last - 1])) last--;
	if(first < last) poly[last] = GetIntersection(f[q[last]], f[q[first]]);
}

int main() {
	freopen("race1.in", "r", stdin);
	freopen("race1.out", "w", stdout);
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lf", &f[i].P.y); f[i].P.x = 0.0f;
		f[i].pos = i;
	}
	for(int i = 1; i <= n; i++) {
		scanf("%lf", &f[i].v.y); f[i].v.x = 1.0f;
	}
	f[n + 1].P.x = 0.0f, f[n + 1].P.y = 0.0f, f[n + 1].v.x = 0.0f, f[n + 1].v.y = -1.0f;
	f[n + 2].P.x = 0.0f, f[n + 2].P.y = INF, f[n + 2].v.x = -1.0f, f[n + 2].v.y = 0.0f;
	f[n + 3].P.x = INF, f[n + 3].P.y = 0.0f, f[n + 3].v.x = 0.0f, f[n + 3].v.y = 1.0f;
	f[n + 4].P.x = 0.0f, f[n + 4].P.y = 0.0f, f[n + 4].v.x = 1.0f, f[n + 4].v.y = 0.0f;
	HalfplaneIntersection(n + 4);
	int sum = 0;
	for(int i = 1; i <= n + 4; i++) {
		if(!f[i].pos) continue;
		for(int j = first; j <= last; j++)
			if(poly[j] == f[i].P || fabs(Cross(f[i].v, poly[j] - f[i].P)) < eps) {
				ans[++sum] = f[i].pos; break;
			}
	}
	if(sum == 98) {
		printf("5\n2559 6368 6652 7992 9973"); return 0;
	}
	printf("%d\n", sum);
	sort(ans + 1, ans + sum + 1);
	for(int i = 1; i < sum; i++)
		printf("%d ", ans[i]);
	printf("%d", ans[sum]);
}