题解:P4479 [BJWC2018] 第k大斜率

张心博harry

2025-01-10 09:33:31

Solution

P4479 [BJWC201] 第k大斜率

思路:

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

{ y_j-y_i \over x_j-x_i } > mid

注意, x_j > x_i

则,

y_j - y_i > mid \times ( x_j - x_i ) y_j - mid \times x_j > y_i - mid \times x_i

对于每个点按照 y - mid \times x 的顺序排序,求二维偏序(顺序对?)即可。

注意点

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