我们将一个人的成绩对应到二维空间中的位置向量，$\vec p_i=(x,y)$，一种排名的计算步骤被抽象为

1. 确定一个法向量$\vec v$， 这个法向量需要满足这些条件：

• $\vec v \cdot \vec v > 0$
• $\vec v$指向第一象限($\vec v[0],\vec v[1]\ge 0$)

2. $\text{GPA}_i=v[0]p[0]+v[1]p[1]=\vec v \cdot \vec p_i$，随后就可以得到小林排名。

为什么这里不需要限制$v[0]+v[1] = 1$呢？这是因为只要$v[0]+v[1] > 0$，计算出来的GPA只是等比例放大缩小，不影响排名。

设小林的位置向量是$\vec Q$，利用$\vec v$当作方向向量的法向量(notice that!)，可以确定一个过$\vec Q$点的直线$\mathbb L(\vec v)$(关于$\vec v$的函数)。

虽然$\mathbb L(\vec v)$千变万化，但是我们并不需要考虑那么多的情况，实际上我们只需要考虑：

• $\mathbb L(\vec v)$经过包括$Q$点的至少两个点
• $\vec v=x \text{ or } y$

设$\text{rank}(\mathbb L)$表示如果确定直线是$\mathbb L$，小林的排名是多少，我们发现使得小林排名最高的$\mathbb L$中，一定至少有一个$\mathbb L_0$经过了包括$Q$点的至少两个点，即"临界条件"(使得$\text{rank}(\mathbb L)$变化)。

而还有两个临界条件，分别就是$x,y$。

此时$O(n^2)$算法就有了，枚举一个点$R$，法向量就是找到个$\vec n ,\text{ s.t. }\vec n\perp \vec {RQ}$（或者$-\vec n$），然后计算所有人的GPA得到小林的排名。记得把$\vec v=(1,0),(0,1)$这几种情况考虑进去。

其实有个$O(n)$做法，在这个基础上优化一下而已。你注意到，在$Q$点右上和左下的点不需要管(Q对他们有绝对劣势或者绝对优势)，只需要考虑左上和右下的点。而左上和右下的点对答案的贡献是关于直线的斜率$k$的分段函数$f$和$h$，分别把$f$和$g$计算出来之后，再$O(n)$枚举斜率，利用双指针找到$f(p)$和$g(q)$统计答案即可。