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

人生第一道紫题题解 qaq

题意

给定平面上 n 个不同的点，要求找出所有存在斜率的直线（即 x_i \neq x_j）并按斜率从大到小排序后，第 k 条直线的斜率的向下取整值。

由于 n 较大（1 \leq n \leq 10^5），暴力 n^2\log n 不可行，需要考虑优化。

思路：二分 + 树状数组

二分斜率：

• 找到一个整数 mid，使得至少有 k 条直线的斜率大于等于 mid，同时小于 mid+1 的直线数量不足 k 条。

那么如何计算斜率 \geq mid 的直线数量呢？

由点斜式方程

得

注意 x_j 必须大于 x_i。

此时不妨将所有点按 x 坐标升序排序。对于每个点 j，计算 c_j = y_j - mid\times x_j。

对所有计算得到的 c_j 离散化后，通过遍历排序后的点，并使用树状数组来统计满足条件的点对数量即可。

注意一点：当 x_i=x_j 时斜率为 0，需要分组处理具有相同 x 坐标的点。对于每个组内的点，先进行查询，再进行更新。

Code

#include <iostream>
#include <algorithm>
#define int long long
#define lowbit(x) x & (-x)
using namespace std;
typedef long long ll;
int sz;
int tr[200005],tx[100010],ty[100010];
int x[100005],y[100005],idx[100005];
void upd(int x,int y=1) {
    while(x<=sz){
        tr[x]+=y;
        x+=lowbit(x);
    }
}
int qry(int x) {
    int res=0;
    while(x>0){
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}
ll cnt_ge(int m,int tx[],int ty[],int n){
    ll c[100010];
    for(int j=0;j<n;j++) 
        c[j]=(ll)ty[j]-(ll)m*tx[j];
    ll srt[100010];
    for(int i=0;i<n;i++) srt[i]=c[i];
    sort(srt,srt+n);
    int unisz=unique(srt,srt+n)-srt;
    int rnk[100010];
    for(int j=0;j<n;j++) 
        rnk[j]=lower_bound(srt,srt+unisz,c[j])-srt+1;
    sz=unisz;
    fill(tr,tr+sz+1,0);
    ll tot=0;
    int j=0;
    while(j<n){
        int cur=tx[j];
        int l=j;
        while(j<n && tx[j]==cur)
            j++;
        int r=j;
        for(int t=l;t<r;t++) 
            tot+=qry(rnk[t]);
        for(int t=l;t<r;t++) 
            upd(rnk[t]);
    }
    return tot;
}
bool cmp(int i, int j) {
    if(x[i]!=x[j]) return x[i]<x[j];
    return y[i]<y[j];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];
    for(int i=0;i<n;i++) idx[i]=i;
    sort(idx,idx+n,cmp);
    for(int i=0;i<n;i++){
        tx[i]=x[idx[i]];
        ty[i]=y[idx[i]];
    }
    int l=-1000000000;
    int r=1000000000;
    int ans=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        ll cnt=cnt_ge(mid,tx,ty,n);
        if(cnt>=(ll)k){
            ans=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    cout<<ans;
    return 0;
}
//不开long long见祖宗。