题解：P4479 [BJWC2018] 第k大斜率

思路

先按 x 从小到大排序。为了防止相同的数影响，如果 x 相等按 y 从大到小排序。

二分斜率 p，查有多少个斜率大于 p，即查有多少个 y_j-y_i>p(x_j-x_i)，这个式子可以写成 y_j-px_j>y_i-px_i。设 t_i=y_i-px_i。当 x_i<x_j 且 t_i<t_j 时斜率大于 p。二维偏序问题，可以用类似求逆序对的方式做，将 t 离散化之后用树状数组维护，开大小为 t 值域的树状数组。

得到的答案就是斜率大于 p 的线的数量 m，用 m 二分。如果 m<k，说明二分到的斜率比较大导致 p 的排序太靠前，使左端点变成 p，否则使右端点变成 p-1。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,k,l,r,b[N],c[N];
struct point{
    int x,y;
}a[N];
struct node{
    int t[N];
    void clear(){
        memset(t,0,sizeof t);
    }
    void add(int x,int y){
        for(int i=x;i<=n;i+=(i&(-i))) t[i]+=y;
    }
    int qry(int x){
        int res=0;
        for(int i=x;i;i-=(i&(-i))) res+=t[i];
        return res;
    }
}A;
bool cmp(point a,point b){
    if(a.x==b.x) return a.y>b.y;
    return a.x<b.x;
}
int check(int p){
    A.clear();
    for(int i=1;i<=n;i++) b[i]=a[i].y-p*a[i].x,c[i]=b[i];
    sort(c+1,c+n+1);
    int m=unique(c+1,c+n+1)-c-1;
    for(int i=1;i<=n;i++) b[i]=lower_bound(c+1,c+m+1,b[i])-c;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cnt+=A.qry(b[i]);
        A.add(b[i],1);
    }
    return cnt;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    l=-1000000000,r=1000000000;
    while(l<r){
        int mid=(l+r+1)/2;
        int tmp=check(mid);
        if(tmp<k) r=mid-1;
        else l=mid;
    }
    cout<<l;
    return 0;
}