还依稀记得半年前的一次模拟赛，这个题我用暴力拿了50分。
旧题重做，现在来谈谈我的做法。
这种问题有个很套路的转化方式——假定一个答案，然后二分答案。
比如对于假定的答案$k$，如果$(i,j) (x_i<x_j)$连线斜率$\geq k$：
设$f(i)=y_i-kx_i$，则可以变为$f(i)\leq f(j)$.
结合上面的$x_i<x_j$，不难发现就是一个二维偏序：先按$f$排序，之后树状数组按$x$ query即可。
但是我刚开始竟然忘了二维偏序怎么写1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
* @Author: Mingyu Li
* @Date: 2019-04-04T17:44:49+08:00
* @Last modified by: Mingyu Li
* @Last modified time: 2019-04-04T20:25:23+08:00
*/
#include <bits/stdc++.h>
#define go(i , x , y) for(register int i = x; i <= y; i++)
#define god(i , y , x) for(register int i = y; i >= x; i--)
using namespace std;
#define ll long long
#define fi first
#define se second
const int N = 100000 + 5;
struct Node {
ll x, y, rwx, ans;
}a[N];
int n,m; ll k;
ll b[N] , c[N];
bool cmp(const Node& u, const Node&v) {
return u.ans == v.ans ? u.rwx < v.rwx : u.ans < v.ans;
}
int query(int x) {
int ans = 0; for(;x; x -= (x & -x)) ans += c[x]; return ans;
}
int upd(int x , int val) {
for(; x<= m; x += (x & -x)) c[x] += val;
}
bool check(int mid) {
go(i,1,n) a[i].ans = a[i].y - 1ll * mid * a[i].x;
sort(a+1,a+n+1,cmp);
memset(c,0,sizeof(c));
ll sum = 0;
go(i,1,n) {
sum += query(a[i].rwx - 1);
upd(a[i].rwx , 1);
}
return sum >= k;
}
int main() {
scanf("%d%lld", &n, &k);
go(i,1,n) {
scanf("%lld%lld", &a[i].x, &a[i].y); b[i] = a[i].x;
}
sort(b+1, b+n+1);
m = unique(b+1,b+n+1) - (b+1);
go(i,1,n) a[i].rwx = lower_bound(b+1,b+m+1,a[i].x) - b;
int l = -(int)(2e8), r = (int)(2e8) , ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)) ans = mid , l = mid + 1;
else r = mid - 1;
}
cout << ans << endl;
return 0;
}