自动搬运

查看原文

来自洛谷，原作者为

	Zilljy258 太沙雕了，，，

搬运于2025-08-24 22:00:37，当前版本为作者最后更新于2025-01-10 09:33:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P4479 [BJWC201] 第k大斜率

思路：

二分斜率，每次检查大于 $mid$ 的斜率个数。

注意，$$ x_j > x_i $$

则，

对于每个点按照 $y - mid \times x$ 的顺序排序，求二维偏序（顺序对？）即可。

注意点

1. 对于 $x$ 相等的两个点，他们的斜率不存在，为了防止被统计到答案中，应当按照 $y$ 从大到小的顺序排序。
2. 每一次二分的 $mid$ 不一样，如果用树状数组的话应该重新进行离散化。