我们将一个人的成绩对应到二维空间中的位置向量，$\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)$统计答案即可。

提供一个 $O(n\log n)$ 的做法

令第 $i$ 个人的两部分成绩分别为 $a_i$ 和 $b_i$，小林则为 $a_1$ 和 $b_1$

令 $c_1=c$，则显然有 $c_2=1-c$，这样我们可以将两个权重简化为一个

排名最高 $\Leftrightarrow$ 小林最终成绩比尽可能多的人高（或等于）

若小林成绩高于或等于第 $i$ 个人：

$$a_1c+b_1(1-c)\geq a_ic+b_i(1-c) \\ (a_1-b_1+b_i-a_i)c\ge b_i-b_1 \\ \left\{\begin{matrix} c\ge \frac{b_i-b_1}{a_1-b_1+b_i-a_i} & a_1-b_1+b_i-a_i>0\\ c\le \frac{b_i-b_1}{a_1-b_1+b_i-a_i} & a_1-b_1+b_i-a_i<0 \\ b_i-b_1\leq 0 & a_1-b_1+b_i-a_i=0 \end{matrix}\right. $$

第三种情况（等于零）特判并排除，其余第 $i$ 个人相当于提供一个值 $v_i = \frac{b_i-b_1}{a_1-b_1+b_i-a_i}$，我们所决定的 $c$ 大于等于或小于等于 $v_i$ 便可获得 $1$ 点价值，并试图令总价值最高。

因此我们将 $v_i$ 排序后暴力枚举 $c$ 处于每个间隔并计算答案即可（枚举 $c$ 处于每个点同样可行）

代码采用分数排序

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int x,y;
int a[5060],b[5060];
struct node
{
	int p,q;
	bool f;
};
node v[5060];
int vl=0;
bool cmp(node x,node y)
{
	if(x.p*y.q==y.p*x.q) return x.f>y.f;//避免多个值相同对结果计算的影响 
	else return x.p*y.q<y.p*x.q;
}
int l1[5060],r0[5060];
int sum=0;
int main()
{
	scanf("%d",&n);
	m=n;
	scanf("%d%d",&x,&y);
	n--;
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++)
	{
		int p,q;
		p=b[i]-y;
		q=x-y+b[i]-a[i];
		if(q>0) v[++vl]=node{p,q,1};
		else if(q<0) v[++vl]=node{p,q,0};
		else
		{
			if(p<=0) sum++;//特判 
		}
	}
	n=vl;
	for(int i=1;i<=n;i++)
	{
		if(v[i].q<0) v[i].q=-v[i].q,v[i].p=-v[i].p;
	}
	sort(v+1,v+n+1,cmp);
	l1[0]=0; r0[n+1]=0;
	for(int i=1;i<=n;i++)
	{
		if(v[i].f) l1[i]=l1[i-1]+1;
		else l1[i]=l1[i-1];
	}
	for(int i=n;i>=1;i--)
	{
		if(!v[i].f) r0[i]=r0[i+1]+1;
		else r0[i]=r0[i+1];
	}
	int ans=0;
	v[0].p=-inf;  v[0].q=1;
	v[n+1].p=inf; v[n+1].q=1;
	for(int i=0;i<=n;i++) //枚举间隔 
	{
		if(v[i+1].p<0||v[i].p>v[i].q) continue;
		ans=max(ans,l1[i]+r0[i+1]);
	}
	/* 
	for(int i=1;i<=n;i++) //枚举点 
	{
		if(v[i].p<0||v[i].p>v[i].q) continue;
		ans=max(ans,l1[i]+r0[i]);
	}
	*/
	printf("%d\n",m-(ans+sum));
	return 0;
}