abc263 Ex - Intersection 2

二分 + 线段相交

---

题意

给定 $n$ 条直线，求所有直线两两之间的交点（重点算多个）中离原点距离第 $k$ 小的点的距离，直线表示为 $A \cdot x + B \cdot y + C = 0$ 。
其中 $1 \leq n \leq 5 \cdot 10^4, - 10^3 \leq |A_i|, |B_i|, |C_i| \leq 10^3$ 。

思路

注意到答案可以二分。
考虑二分答案，记二分值为 $mid$ ，作原点为圆心， $mid$ 为半径的圆，问题转换为求圆内的直线的交点个数。
每条直线与圆的两个交点可以转换为一个区间 $[l, r]$ ，两直线交点在圆内等价于两直线代表的区间部分相交，问题转换为求区间对 $[l_i, r_i], [l_j, r_j]$ 的个数，区间满足 $l_i \leq l_j \leq r_i \leq r_j$ ，按右端点排序后套树状数组求即可。

代码

主要部分

int n,K;
Line line[maxp];
struct BIT{
    int n;
    int bit[maxp*2];
    void init(int _n){
        n=_n;
        for(int i=1;i<=n;i++) bit[i]=0;
    }
    void add(int x,int k){
        for(int i=x;i<=n;i+=(i&-i)) bit[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i;i-=(i&-i)) res+=bit[i];
        return res;
    }
}bit;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>K;
    for(int i=1;i<=n;i++){
        double a,b,c;
        cin>>a>>b>>c;
        line[i]=Line(a,b,c);
    }
    double l=0,r=2*sqrt(2)*1e6;
    while(r-l>eps){
        double mid=(l+r)/2;

        auto calc=[&](double mid){
            circle c(Point(0,0),mid);
            vector<pdd> sta;
            vector<double> app;
            vector<pii> vec;
            for(int i=1;i<=n;i++){
                Point p1,p2;
                if(c.pointcrossline(line[i],p1,p2)==0) continue;
                double l,r;
                if(p1.y>0) l=Point(0,0).rad(Point(1,0),p1)*mid;
                else l=(Point(0,0).rad(Point(-1,0),p1)+pi)*mid;
                if(p2.y>0) r=Point(0,0).rad(Point(1,0),p2)*mid;
                else r=(Point(0,0).rad(Point(-1,0),p2)+pi)*mid;
                if(l>r) swap(l,r);
                sta.push_back({l,r});
                app.push_back(l);
                app.push_back(r);
            }
            sort(app.begin(),app.end());
            app.erase(unique(app.begin(),app.end()),app.end());
            for(auto [dl,dr]:sta){
                int l=lower_bound(app.begin(),app.end(),dl)-app.begin()+1;
                int r=lower_bound(app.begin(),app.end(),dr)-app.begin()+1;
                vec.push_back({l,r});
            }
            sort(vec.begin(),vec.end(),[&](const pii &a,const pii &b){
                return a.second<b.second;
            });
            ll res=0;
            bit.init(app.size()+5);
            for(auto [l,r]:vec){
                res+=bit.sum(l);
                bit.add(l,1);
                bit.add(r+1,-1);
            }
            return res;
        };

        if(calc(mid)>=K) r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(8)<<r;

    return true&&false;
}