[BJWC2018] 第k大斜率
题目描述
在平面直角坐标系上,有 $n$ 个不同的点。任意两个不同的点确定了一条直线。请求出所有斜率存在的直线按斜率从大到小排序后,第 $k$ 条直线的斜率为多少。
为了避免精度误差,请输出斜率向下取整后的结果。(例如:$\lfloor 1.5 \rfloor = 1$,$\lfloor -1.5 \rfloor = -2$)。
输入输出格式
输入格式
第一行,包含两个正整数 $n$ 和 $k$。
接下来 $n$ 行,每行包含两个整数 $x_i, y_i$,表示每个点的横纵坐标。
输出格式
输出一行,包含一个整数,表示第 $k$ 大的斜率向下取整的结果。
输入输出样例
输入样例 #1
4 1
-1 -1
2 1
3 3
1 4
输出样例 #1
2
说明
**【样例说明】**
符合要求的直线的斜率分别为 $-3, -\frac{1}{2}, \frac{2}{3}, 1, 2, \frac{5}{2}$ 。
**【数据规模和约定】**
令 $M$ 为所有斜率存在的直线的数量 。
对于 $10 \%$ 的数据,$1 \le n \le 10$。
对于 $20 \%$ 的数据,$1 \le n \le 100$,$|x_i|, |y_i| \le {10}^3$。
对于 $30 \%$ 的数据,$1 \le n \le 1000$。
对于 $40 \%$ 的数据,$1 ≤ n ≤ 5000$。
对于另 $20 \%$ 的数据,满足 $k = 1$ 。
对于另 $20 \%$ 的数据,满足 $1 \le x_i, y_i \le {10}^3$。
对于 $100 \%$ 的数据,$1 \le n \le 100000$,$1 \le k \le M$,$|x_i|, |y_i| \le {10}^8$。