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 的顺序排序,求二维偏序(顺序对?)即可。
注意点
- 对于 x 相等的两个点,他们的斜率不存在,为了防止被统计到答案中,应当按照 y 从大到小的顺序排序。
- 每一次二分的 mid 不一样,如果用树状数组的话应该重新进行离散化。