题解
能够排名第 $k$ 的一定满足：存在一个 $x$，使得分数比这个人高的人不超过 $k-1$ 个。可以枚举其它的每一个人，然后计算它比这个人优秀的 $x$ 区间，最后检查一下被覆盖次数最小的部分被覆盖了多少次即可。这样是 $O(n^2 \log n)$ 的。
由于 $m$ 很小，我们考虑对每个 $k\in [1,m]$ 分别求解。假设现在已经求出了排名为 $1$ 到 $k-1$ 的人，则排名为 $k$ 的人一定在剩下的人的半平面交上，并且让它能进队的 $x$ 也一定在半平面交中它贡献的线段上。对其它人求出：对于哪些 $x$，它会比半平面交上对应位置的直线优秀；由于半平面交的形状是个凸壳，所以这样的 $x$ 一定也会构成一个连续区间。而一个人的排名为 $k$ 的条件就是：半平面交中它贡献的线段上，存在整点 $x$，满足 $x$ 只被那些区间覆盖了不到 $k$ 次。时间复杂度 $O(nm\log n)$。
代码实现
排名为“分数严格大于自己的人数+1”，所以：
- 对每个人求出的可以覆盖的 $x$ 区间，其端点是不能取到的
- 半平面交中，如果三条直线交于一点，则三条直线都应该保留
题目中要求 $x$ 为非负整数，所以要特殊判断半平面交中的某条线段上没有整点的情况
判断某个人是否排名为 $k$：事先求出所有的被覆盖次数不到 $k$ 的区间（称为好区间），然后检查这些好区间与这个人在半平面交上的区间是否有交，这个可以转化成判断与这个人在半平面交上的区间无交的好区间数量是否等于总数量。
（似乎）
long double会精度爆炸，所以用了两个__int128来表示一个分数。从 cz_xuyixuan 的代码中学到了一个很妙的判断直线和凸壳上的点的位置关系的实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33struct frac {
__int128 a,b;
frac(__int128 a=0,__int128 b=1): a(a),b(b) {}
friend bool operator <(frac A,frac B) { return A.a*B.b < A.b*B.a; }
friend bool operator <=(frac A,frac B) { return A.a*B.b <= A.b*B.a;
}s[N];
struct Line {
ll k,b;
}q[N],L[N];
int tl;
inline frac INTER(Line A,Line B) {
if(B.k>A.k) return frac(A.b-B.b,B.k-A.k);
else return frac(B.b-A.b,A.k-B.k);
}
bool cmp(int x,int y) {
if(L[x].k!=L[y].k) return L[x].k<L[y].k;
return L[x].b>L[y].b;
}
// p 为要求半平面交的直线的编号
inline void HPI(vector<int> &p) {
sort(p.begin(),p.end(),cmp);
tl=0;
for(int i=0;i<p.size();++i) {
Line c=L[p[i]];
if(tl&&c.k==L[p[i-1]].k) continue;
while(tl>=2 && INTER(q[tl],c)<s[tl]) tl--;
while(tl>=1 && q[tl].b<c.b) tl--;
q[++tl]=c;
if(tl==1) s[tl]=frac(0,1);
else s[tl]=INTER(q[tl],q[tl-1]);
}
s[tl+1]=frac(inf,1);
}