P4479 [BJWC2018] The k-th Largest Slope

On the 2D Cartesian plane, there are $n$ distinct points. Any two distinct points determine a line. Among all lines whose slopes are defined, sort them by slope in descending order and find the slope of the $k$-th line. To avoid precision errors, please output the floor of the slope. (For example: $\lfloor 1.5 \rfloor = 1$, $\lfloor -1.5 \rfloor = -2$.)

The first line contains two positive integers $n$ and $k$. Each of the next $n$ lines contains two integers $x_i, y_i$, the coordinates of a point.

Output one line containing an integer: the floor of the $k$-th largest slope.

[Sample Explanation] The slopes of the lines that meet the requirement are $-3, -\frac{1}{2}, \frac{2}{3}, 1, 2, \frac{5}{2}$. [Constraints] Let $M$ be the number of lines whose slopes are defined. - For $10\%$ of the testdata, $1 \le n \le 10$. - For $20\%$ of the testdata, $1 \le n \le 100$, $|x_i|, |y_i| \le 10^3$. - For $30\%$ of the testdata, $1 \le n \le 1000$. - For $40\%$ of the testdata, $1 \le n \le 5000$. - For another $20\%$ of the testdata, $k = 1$. - For another $20\%$ of the testdata, $1 \le x_i, y_i \le 10^3$. - For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le k \le M$, $|x_i|, |y_i| \le 10^8$. Translated by ChatGPT 5