记录编号	196251	评测结果	AAAAAAAAAAAA
题目名称	[USACO Jan07]考试	最终得分	100
用户昵称	luoyuchu	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2015-10-21 11:18:14	内存使用	2.22 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <ctime>
#include <map>
#include <set>

#define dig(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

template <class TAT>
void read(TAT &a)
{
	static char cc;
	static bool fff;
	while (((cc = getchar()) < '0' || cc > '9') && cc != '-');
	if (cc == '-') fff = 1, a = 0;
	else fff = 0, a = cc - 48;
	while ((cc = getchar()) >= '0' && cc <= '9') a = a * 10 + cc - 48;
	if (fff) a = -a;
}
template <class TAT>
void write(TAT a)
{
	static char cc[25];
	static int ct;
	if (a == 0) {putchar('0'); return;}
	if (a < 0) {putchar('-'); a = -a;}
	ct = 0;
	while (a) {cc[++ct] = a % 10 + 48; a /= 10;}
	while (ct) {putchar(cc[ct--]);}
}
void begin()
{
	freopen("schul.in", "r", stdin);
	freopen("schul.out", "w", stdout);
}
void end()
{
	fclose(stdin);
	fclose(stdout);
}
template <class TAT>
void Ckmin(TAT &a, const TAT &b)
{
	if (a > b) a = b;
}
template <class TAT>
void Ckmax(TAT &a, const TAT &b)
{
	if (a < b) a = b;
}

const int maxn = 50005;

int n;
struct Point
{
	int x, y;
	Point() {}
	Point(int xx, int yy):x(xx), y(yy) {}
	Point operator - (const Point &b) const
	{
		return Point(x - b.x, y - b.y);
	}
}dot[maxn];
int cross(const Point &a, const Point &b)
{
	return (a.x * b.y - a.y * b.x);
}
bool cmp_Bigger(const Point &a, const Point &b)
{
	return (a.y * b.x < b.y * a.x);
}
bool cmp_Less(const Point &a, const Point &b)
{
	return (a.y * b.x > b.y * a.x);
}
double xie[maxn] = {0};
double worst[maxn] = {0};
double best[maxn] = {0};
Point stack[maxn];
int st = 0;

void Init()
{
	register int i, j, k;
	read(n);
	for (i = 1; i <= n; ++i)
	{
		read(dot[i].y);
		read(dot[i].x);
	}
}

void PrepareWorst()
{
	register int i, j, k;
	register int Sx = 0, Sy = 0;
	sort(dot + 1, dot + 1 + n, cmp_Less);
	for (i = 1; i <= n; ++i)
	{
		Sx += dot[i].x;
		Sy += dot[i].y;
		xie[i] = Sy / (double)Sx;
	}
	st = 0;
	for (i = 1; i <= n; ++i)
	{
		while (st >= 1 && stack[st].x <= dot[i].x) --st;
		while (st >= 2 && cross(stack[st] - stack[st - 1], dot[i] - stack[st]) >= 0) --st;
		stack[++st] = dot[i];
		while (st >= 2 && (stack[st].y - stack[st - 1].y) > xie[i] * (stack[st].x - stack[st - 1].x)) --st;
		worst[i] = stack[st].y - stack[st].x * xie[i];
	}
	reverse(xie + 1, xie + n);
	reverse(worst + 1, worst + n);
}

void PrepareBest()
{
	register int i, j, k;
	sort(dot + 1, dot + 1 + n, cmp_Bigger);
	st = 0;
	for (i = 1; i <= n; ++i)
	{
		while (st >= 1 && stack[st].x >= dot[i].x) --st;
		while (st >= 2 && cross(stack[st] - stack[st - 1], dot[i] - stack[st]) >= 0) --st;
		stack[++st] = dot[i];
		while (st >= 2 && (stack[st].y - stack[st - 1].y) < xie[i] * (stack[st].x - stack[st - 1].x)) --st;
		best[i] = stack[st].y - stack[st].x * xie[i];
	}
}

void Solve()
{
	register int i, j, k;
	register int cnt = 0;
	for (i = 1; i < n; ++i)
	{
		if (best[i] > worst[i])
		{
			++cnt;
		}
	}
	write(cnt); putchar('\n');
	for (i = 1; i < n; ++i)
	{
		if (best[i] > worst[i])
		{
			write(i);
			putchar('\n');
		}
	}
}

int main()
{
	begin();
	Init();
	PrepareWorst();
	PrepareBest();
	Solve();
	end();
	return 0;
}