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

思路

对于本题，优先考虑暴力。
暴力：O(n^2) 暴力枚举每个点的组合，再进行排序，时间复杂度 O(n^2\log n)。

考虑优化：将问题转化一下，从求第 k 大的转化为求斜率为 P 的是斜率第几大的。
我们表示一下斜率大于 P 的两点的斜率，即：

则我们按照 x 排序，以保证 x_i-x_j 为正数，将 x_i-x_j 乘到另一边，则：

将同类移到一边：

则对于 T_i=(y_i-P\times x_i) 中 T_i 与 T_j 构成二维偏序，可用树状数组或归并排序实现。
我们已经可以实现求斜率为 P 的是斜率第几大的，因为答案具有单调性，二分答案即可。

代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e5+9;
struct node{
    int x,y;
    bool operator <(const node &a)const{
        if(a.x==x) return y>a.y;
        return x<a.x;
    }
}a[N];
int cqr[N],t[N];
int n,k,cnt;
void ssort(int l,int r){
    int mid=(l+r)>>1;
    if(l==r)
        return;
    ssort(l,mid);
    ssort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(cqr[i]<=cqr[j]){
            cnt+=(r-j+1);
            t[k++]=cqr[i++];
        }
        else
            t[k++]=cqr[j++];
    }
    while(i<=mid)
        t[k++]=cqr[i++];
    while(j<=r)
        t[k++]=cqr[j++];
    for(int p=l;p<=r;p++)
        cqr[p]=t[p];
}
bool check(int p){
    for(int i=1;i<=n;i++){
        cqr[i]=a[i].y-p*a[i].x;
    }
    cnt=0;
    ssort(1,n);
    return cnt>=k;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+1+n);
    int l=-INF,r=INF,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}