记录编号	196438	评测结果	AAAAAAAAAAAA
题目名称	[USACO Jan07]考试	最终得分	100
用户昵称	ppfish	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2015-10-21 19:34:12	内存使用	3.79 MiB

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int bufsize = 1 << 20;

char buf[bufsize], *ins = buf, *ous = buf;

inline char getc()
{
    if (ins == ous) ins = buf, ous = buf + fread(buf, 1, bufsize, stdin);
    return *ins ++;
}

template<class T>inline void Read(T &x)
{
    int f = 1;
    char t = getc();
    while (t < '0' || t > '9') {
        if (t == '-') f = -1;
        t = getc();
    }
    x = 0;
    while (t >= '0' && t <= '9') {
        x = x * 10 + t - '0';
        t = getc();
    }
    x *= f;
}

const int maxn = 50005;

struct point {
    int P, T; // x, y
    point() {}
    point(int P, int T) : P(P), T(T) {}
    point operator + (const point &rhs) { return point(P + rhs.P, T + rhs.T); }
    point operator - (const point &rhs) { return point(P - rhs.P, T - rhs.T); }
    point operator * (const double v) { return point(P * v, T * v); }
    point operator / (const double v) { return point(P / v, T / v); }
    bool operator < (const point &rhs) const { return T * rhs.P < P * rhs.T; }
};

int n, q[maxn], r;
double mx[maxn], mn[maxn], sumu[maxn], sumd[maxn], ratio[maxn];
point g[maxn];

vector<int> ans;

void input()
{
    Read(n);
    for (register int i = 1; i <= n; i++) Read(g[i].T), Read(g[i].P);
    sort(g + 1, g + n + 1);
    for (register int i = n; i >= 1; i--) {
        sumu[i] = sumu[i + 1] + g[i].T, sumd[i] = sumd[i + 1] + g[i].P;
        ratio[i] = sumu[i] / sumd[i];
    }
}

inline long long cross(const point &a, const point &b)
{
    return a.P * b.T - a.T * b.P;
}

inline double calc(const point &pts, double x)
{
    return (double) pts.T - pts.P * x;
}

void solve()
{
    // for (register int i = 1; i <= n; i++) printf("%.2f %.2f %.2f\n", g[i].P, g[i].T, g[i].T / g[i].P);
    double ratioNow;
    r = 0;
    for (register int i = 1; i <= n; i++) {
        // d = i
        ratioNow = ratio[i + 1];
        while (r > 0 && g[q[r]].P >= g[i].P) r --;
        while (r > 1 && cross(g[i] - g[q[r]], g[q[r]] - g[q[r - 1]]) <= 0) r --;
        q[++r] = i;
        while (r > 1 && calc(g[q[r]], ratioNow) <= calc(g[q[r - 1]], ratioNow)) r --;
        mx[i] = g[q[r]].T - g[q[r]].P * ratioNow;
        //printf("d = %d, %.3f %.3f\n", i, ratioNow, mx[i]);
    }
    r = 0;
    for (register int i = n; i >= 2; i--) {
        // d = i - 1
        ratioNow = ratio[i];
        while (r > 0 && g[q[r]].P <= g[i].P) r --;
        while (r > 1 && cross(g[q[r]] - g[i], g[q[r - 1]] - g[q[r]]) <= 0) r --;
        q[++r] = i;
        while (r > 1 && calc(g[q[r]], ratioNow) >= calc(g[q[r - 1]], ratioNow)) r --;
        mn[i - 1] = g[q[r]].T - g[q[r]].P * ratioNow;
        //printf("d = %d, %.3f %.3f %.3f\n", i - 1, ratioNow, mx[i - 1], mn[i - 1]);
    }
    for (register int i = 1; i < n; i++) if (mn[i] < mx[i]) ans.push_back(i);
    printf("%d\n", (int) ans.size());
    for (register int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]);
}

int main()
{
    //#ifndef ONLINE_JUDGE
    freopen("schul.in", "r", stdin);
    freopen("schul.out", "w", stdout);
    //#endif

    input();
    solve();

#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;
}