#include #include using namespace std; #define ll long long #define LIM 100111 #define MAXANS 1e10 #define EPS 1e-5 struct line { // y = mx + b double m, b; double intercept(double y) { return (y - b) / m; } }; int pos[LIM]; int bago[LIM]; int orig[LIM]; line lines[LIM]; double intercept[LIM]; int n; ll inversions() { for (int i = 0; i < n; i++) bago[i] = pos[bago[i]]; // number of inversions in 'bago' #define fenwick orig for (int i = 0; i <= n; i++) fenwick[i] = 0; ll ans = 0; for (int i = n-1; i >= 0; i--) { for (int v = bago[i]+1; v; v ^= v & -v) { ans += fenwick[v]; } for (int v = bago[i]+1; v <= n; v += v & -v) { fenwick[v]++; } } return ans; #undef fenwick } bool comp(int i, int j) { return intercept[i] < intercept[j]; } void get_order(int *indices, double y) { // get order of intercepts at the line "y = y" for (int i = 0; i < n; i++) { intercept[i] = lines[i].intercept(y); } sort(indices, indices + n, comp); } int main() { ll k; scanf("%d%lld", &n, &k); for (int i = 0; i < n; i++) { scanf("%lf%lf", &lines[i].m, &lines[i].b); bago[i] = orig[i] = i; } get_order(orig, -MAXANS); for (int i = 0; i < n; i++) pos[orig[i]] = i; double L = -MAXANS, R = +MAXANS; while (R - L > EPS) { double M = 0.5 * (L + R); get_order(bago, M); (inversions() < k ? L : R) = M; } printf("%.11lf\n", L); }