题意：
Bessie考了N科（N≤50000），每科的得分为Ti，满分为Pi（样例似乎是五科红灯……）。
现在Bessie的老师要给她们统计最终得分，方法 是先算出每一科得分的百分比，去除D个百分比最低的科目，然后剩下科目的∑T / ∑P就是最终得分的百分比。
很幸运，没有人有两科的得分比一样。Bessie的数学很牛X，她马上就发现她的老师在坑爹，因为有时候可以通过去除不同的科 目来获得更高的分数。
现在Bessie想知道，对于哪些D值，她可以通过去除与老师不同的D科，从而获得更高的分数呢？
（摘自http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html）
做法：
假设现在取了i个百分比靠前的科目，当前的综合百分比是k。
如果能把选的科目p替换成一个没选的科目q使得综合百分比提高 ，根据01分数规划的思想，显然 p.T-k*p.P<q.T-k*q.P 。
于是就可以在选的科目中找一个科目 p 使得 p.T-k*p.P最小，再在没选的科目中找一个科目 q 使 q.T-k*q.P 最大 。
然后发现 T-k*P 就是向量的点积 （1,-k)*(T,P) ，就可以用平衡树维护两个凸壳来找最大值和最小值。
注意到：排序后 选的科目越多，综合百分比越低，因此k是单调的，于是便不需要在平衡树里二分查找了。
网上题解说可以用单调栈，但是总感觉有问题，还是用了平衡树。
我依旧是把上凸壳转化成下凸壳用同一个函数来做。
#include<cstdio>
#include<map>
#include<algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef map<int,int>::iterator itr;
const int N=50005;
int n;
double k[N],fmax[N],fmin[N];
int ans[N];
struct P
{
int x,y;
P operator-(const P &t)const
{
return {x-t.x,y-t.y};
}
int operator^(P t)
{
return x*t.y-y*t.x;
}
}a[N];
bool cmp(P a,P b)
{
return 1.0*a.y/a.x>1.0*b.y/b.x;
}
double dot(itr it,double x,double y)
{
return it->X*x+it->Y*y;
}
ll cross(itr l,P p2,itr r)
{
P p1={l->X,l->Y},p3={r->X,r->Y};
return (p2-p1)^(p3-p2);
}
struct hull
{
map<int,int>s;
itr mid,l,r,p1,p2;
void init() { s.clear(); }
itr pre(itr it)
{
if (it==s.end()) return it;
if (it==s.begin()) return s.end();
return --it;
}
itr suc(itr it)
{
if (it==s.end()) return it;
return ++it;
}
bool inside(P p)
{
if (s.empty()) return 0;
r=s.lower_bound(p.x);
if (r==s.end()) return 0;
if (r->X==p.x) return p.y>=r->Y;
if (r==s.begin()) return 0;
l=r; l--;
return cross(l,p,r)<=0;
}
void add(P p)
{
if (inside(p)) return;
s[p.x]=p.y;
mid=s.find(p.x);
p1=suc(mid); p2=suc(p1);
while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)<=0)
s.erase(p1),p1=p2,p2=suc(p2);
p1=pre(mid); p2=pre(p1);
while(p1!=s.end()&&p2!=s.end()&&cross(mid,{p1->X,p1->Y},p2)>=0)
s.erase(p1),p1=p2,p2=pre(p2);
}
double get(double x,double y)
{
r=s.end(); r--;
l=pre(r);
while(l!=s.end()&&dot(l,x,y)<=dot(r,x,y))
s.erase(r),r=l,l=pre(l);
return dot(r,x,y);
}
}G;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i].y,&a[i].x);
sort(a+1,a+n+1,cmp);
double sumT=0,sumP=0;
for (int i=1;i<=n;i++) sumT+=a[i].y,sumP+=a[i].x,k[i]=sumT/sumP;
G.init();
for (int i=1;i<=n;i++)
{
G.add(a[i]);
fmin[i]=G.get(-k[i],1);
}
G.init();
for (int i=n;i>=2;i--)
{
G.add({a[i].x,-a[i].y});
fmax[i-1]=-G.get(k[i-1],1);
}
int cnt=0;
for (int i=1;i<n;i++)
if (fmin[i]<fmax[i]) ans[++cnt]=n-i;
printf("%d\n",cnt);
for (int i=cnt;i>=1;i--) printf("%d\n",ans[i]);
}
