题意理解

我们有 $n$ 个选手，第 $i$ 个选手的属性为 $(a_i, b_i)$。
对于非负整数 $x$，选手 $i$ 的表现值为：

$$f_i(x) = a_i \cdot x + b_i$$

选手 $i$ 的排名定义为：

$$\text{rank}_i(x) = 1 + \{j \mid f_j(x) > f_i(x)\}$$

省队名额为 $m$，即 $\text{rank}_i(x) \le m$ 才能进队。

我们需要对每个 $i$：

• 判断是否存在 $x \ge 0$ 使得 $\text{rank}_i(x) \le m$；
• 如果能，求 $\min_{x \ge 0} \text{rank}_i(x)$。

---

关键观察

1. 比较两个选手的表现

对于选手 $i$ 和 $j$，比较 $f_i(x)$ 与 $f_j(x)$： [ a_i x + b_i > a_j x + b_j \quad \Leftrightarrow \quad (a_i - a_j) x > b_j - b_i ] 这是一个关于 $x$ 的线性不等式。

• 如果 $a_i = a_j$，则大小关系由 $b_i$ 与 $b_j$ 决定，与 $x$ 无关。
• 如果 $a_i \ne a_j$，则存在一个临界点 $x_0 = \frac{b_j - b_i}{a_i - a_j}$，在 $x_0$ 两侧大小关系相反。

因此，每个 $(i,j)$ 对最多在某个 $x$ 处发生一次表现值的大小反转。

---

2. 排名的变化性质

当 $x$ 从 $0$ 增加到 $+\infty$ 时，排名只在有限个临界点发生变化。
这些临界点是所有 $\frac{b_j - b_i}{a_i - a_j}$ 中非负的有理数（或实数，但可离散化）。

因此，$x$ 的有效取值可以看作：$0$、临界点、以及临界点之间的区间代表点、$+\infty$。

---

3. 问题转化

对于选手 $i$，我们想知道：

• 是否存在 $x \ge 0$ 使得不超过 $m-1$ 个人的表现严格大于他。
• 等价地：存在 $x$ 使得严格大于他的人 $\le m-1$。

记 $S_i(x) = \{ j \mid f_j(x) > f_i(x) \}$，$|S_i(x)| \le m-1$。

---

解法思路

步骤 1：按 $a_i$ 分类

将选手按 $a_i$ 分组，同组内按 $b_i$ 排序。

对于 $x \to +\infty$，表现值的大小主要由 $a_i$ 决定：

• $a_i$ 大的选手，当 $x$ 很大时表现值大。
• $a_i$ 相同则按 $b_i$ 大小决定。

---

步骤 2：考虑 $x=0$ 和 $x \to \infty$

当 $x=0$ 时，表现值就是 $b_i$，排名按 $b_i$ 降序排列。

当 $x \to +\infty$ 时，表现值主要由 $a_i$ 决定，$a_i$ 大的排前面，$a_i$ 相同时按 $b_i$ 降序。

---

步骤 3：选手 $i$ 能进队的条件

选手 $i$ 能进队，当且仅当存在 $x \ge 0$ 使得 $|S_i(x)| \le m-1$。

考虑 $x=0$ 和 $x \to +\infty$ 两个极端：

• 如果在 $x=0$ 时 $|S_i(0)| \le m-1$，则直接可以进队。
• 如果在 $x \to +\infty$ 时 $|S_i(\infty)| \le m-1$，也可以进队。
• 否则，如果在某个中间 $x$ 处 $|S_i(x)| \le m-1$，也可以进队。

---

步骤 4：如何求可能的最好排名

最好排名是：

$$\min_{x \ge 0} \left( 1 + |S_i(x)| \right)$$

即最小化严格大于他的人数 $|S_i(x)|$。

---

步骤 5：$m=1$ 的特殊情况

当 $m=1$ 时，只有排名第 1 才能进队。
即必须存在 $x$ 使得 $|S_i(x)| = 0$，即 $f_i(x)$ 是最大值（可能并列）。

结论：$m=1$ 时，能进队的选手必须是在所有 $x \ge 0$ 中，可能成为表现值最大的人（即在上凸壳上）。

---

步骤 6：一般情况下的高效算法

我们可以用扫描线方法：

1. 将所有选手按 $a_i$ 分组，组内按 $b_i$ 降序。
2. 考虑 $x$ 从 $0$ 增加到 $+\infty$ 的过程，维护当前排名。
3. 排名变化只发生在临界点，即两个选手的表现值相等的 $x$ 值。
4. 对每个选手，记录其排名的最小值。

具体实现时：

• 我们只关心每个选手的排名变化，可以枚举 $x$ 的候选值（所有临界点和两个端点）。
• 但临界点有 $O(n^2)$ 个，需要优化。

---

步骤 7：优化

注意到，当 $x$ 变化时，排名变化是交换相邻的选手（如果按 $f_i(x)$ 排序）。
因此，我们可以用“交换逆序对”的方式来考虑：
初始时按 $x=0$ 排序（即按 $b_i$ 降序），然后当 $x$ 增加时，某些 $(i,j)$ 会交换位置，如果 $a_i < a_j$ 且初始 $b_i > b_j$，则当 $x$ 超过 $\frac{b_i - b_j}{a_j - a_i}$ 时，$j$ 会超过 $i$。

这样，我们只需要考虑 $O(n^2)$ 个交换事件，但可以用归并排序式的方法减少事件数。

---

步骤 8：最终算法框架

1. 初始按 $b_i$ 降序排列得到排名。
2. 找出所有可能的交换事件（即相邻的逆序对在某个 $x$ 处交换），用优先队列处理。
3. 在 $x$ 变化过程中维护每个人的排名，并记录其最佳排名。
4. 最后输出：如果最佳排名 $\le m$ 则输出最佳排名，否则输出 $-1$。

---

公式总结

• 表现值：$f_i(x) = a_i x + b_i$
• 排名：$\text{rank}_i(x) = 1 + \{j \mid f_j(x) > f_i(x)\}$
• 临界点（$i$ 与 $j$ 表现相等）：$x = \frac{b_j - b_i}{a_i - a_j}$（当 $a_i \ne a_j$ 且符号使 $x \ge 0$）
• 比较规则：$f_i(x) > f_j(x) \iff (a_i - a_j) x > b_j - b_i$

---

时间复杂度

如果暴力枚举所有 $O(n^2)$ 临界点，复杂度 $O(n^3)$ 或 $O(n^2 \log n)$，在 $n \le 200$ 时可过。
对于 $n$ 大的情况，需要更高效的扫描线维护，最优可做到 $O(n \log n)$ 或 $O(n \log^2 n)$。