记录编号	195884	评测结果	AAAAAAAAAAAA
题目名称	[USACO Jan07]考试	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2015-10-20 01:37:14	内存使用	2.21 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
 
template<class Num>void read(Num &x)
{
    char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -1;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<3) + (x<<1) + (c-'0');
    x *= flag;
}
template<class Num>void write(Num x)
{
    if(!x) {putchar('0');return;}
    if(x < 0) putchar('-'), x = -x;
    static char s[20];int sl = 0;
    while(x) s[sl++] = x%10 + '0',x /= 10;
    while(sl) putchar(s[--sl]);
}
 
const int maxn = 50010;
#define X second.first
#define Y second.second
#define R first
const double lim = 40050;
 
int n;
std::pair<double, std::pair<int,int> >node[maxn];
double low[maxn], high[maxn];
double G[maxn];
 
void init()
{
	int x, y;
	
	read(n);
	
	for(int i = 1; i <= n; i++)
	{
		read(y), read(x);
		node[i] = std::make_pair((double) y / x , std::make_pair(x, y));
	}
}
double slope(int a,int b)
{
	return (double)(node[b].Y - node[a].Y) / (node[b].X - node[a].X);
}
void solve()
{
	static int line[maxn];
	int f = 0, r = 0, cnt = 0;
	
	std::sort(node + 1, node + n + 1);
//std::greater<std::pair<double, std::pair<int,int> > >()	
	for(int i = n, tx = 0, ty = 0; i >= 1; i--)
	{
		tx += node[i].X, ty += node[i].Y;
		G[i] = (double) ty / tx;
	}
	
	f = r = 0;
	for(int i = 1; i < n; i++)
	{
		while(f != r && node[line[r - 1]].X >= node[i].X) r--;
		while(r - f >= 2 && slope(line[r - 2], i) > slope(line[r - 2], line[r - 1])) r--;
		line[r++] = i;
		while(r - f >= 2 && slope(line[r - 2], line[r - 1]) < G[i + 1]) r--;
		high[i] = node[line[r - 1]].Y - G[i + 1] * node[line[r - 1]].X;
	}
	f = r = 0;
	for(int i = n; i > 1; i--)
	{
		while(f != r && node[line[r - 1]].X <= node[i].X) r--;
		while(r - f >= 2 && slope(line[r - 2], i) > slope(line[r - 2], line[r - 1])) r--;
		line[r++] = i;
		while(r - f >= 2 && slope(line[r - 2], line[r - 1]) < G[i]) r--;
		low[i] = node[line[r - 1]].Y - G[i] * node[line[r - 1]].X;
	}
	
	for(int i = 1; i < n; i++)
		cnt += low[i + 1] < high[i];
	write(cnt), puts("");
	for(int i = 1; i < n; i++)	
		if(low[i + 1] < high[i])
			write(i), puts("");
}
int main()
{
	freopen("schul.in","r",stdin);
	freopen("schul.out","w",stdout);
	
	init();
	
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}