CF1446F 【Line Distance】

· · 题解

首先答案肯定可以二分，\rm check(R) 时我们需要求多少条直线与 (0,0) 相距 \le R 。

然后画画图，感觉很难统计。

这里要用到一个神仙转化：

以 (0,0) 为圆心，R 为半径画个圆，圆内/圆上的点与其他点连线一定距离 \le R，这样只要考虑圆外的点。

每个圆外的点对圆作两条切线，可以得到一段圆弧。

两个圆外的点 (x_i,y_i),(x_j,y_j) 连线与 (0,0) 距离 > R，当且仅当它们投射的两段圆弧有交集且不包含。

如图，可以观察一下 CD 与 CE

于是问题转化为，在圆上有若干圆弧，求有多少对圆弧相交但不包含。

这样看起来可做多了，但是似乎不太好处理。

于是蒟蒻乱画了一下，得到另一个性质：一段圆弧翻转以后，对答案没有影响。

那就在圆上某点拆开，拆成一条直线，如果有跨越这个点两段的圆弧就翻转。

然后离散化+树状数组维护即可，O(n\log n\log V)

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
//#define double long double
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
#define maxn 200005
const double pi=3.14159265358979323846,eps=1e-8;
int n,m,l[maxn],r[maxn];
double a[maxn],b[maxn],t[maxn],tl[maxn],tr[maxn];
bool vis[maxn];
int c[maxn],p[maxn],k;
bool cmp(int x,int y){return l[x]<l[y];}
inline void add(int x,int y){
    for(;x<=m;x+=x&-x)c[x]+=y;
}
inline int ask(int x){
    int res=0;
    for(;x;x^=x&-x)res+=c[x];
    return res;
}
inline int ask(int l,int r){return ask(r)-ask(l-1);}

long long check(double rd)
{
    long long res=0,in=0; m=0;k=0;
    For(i,1,n)vis[i]=0; 
    For(i,1,n){
        double x=a[i],y=b[i],dis=sqrt(x*x+y*y);
        if(dis<rd+eps){in++;vis[i]=1;continue;}
        double ang=atan2(y,x),dt=acos(rd/dis);
        tl[i]=ang-dt,tr[i]=ang+dt;
        if(tl[i]<-pi)tl[i]+=pi*2;
        if(tr[i]>pi)tr[i]-=pi*2;
        if(tl[i]>tr[i])swap(tl[i],tr[i]);
        t[++m]=tl[i],t[++m]=tr[i];
    //  printf("%d %.4Lf %.4Lf\n",i,tl[i],tr[i]); 
    }
    sort(t+1,t+m+1);
    For(i,1,n){
        if(vis[i])continue;
        p[++k]=i;
        l[i]=lower_bound(t+1,t+m+1,tl[i])-t;
        r[i]=lower_bound(t+1,t+m+1,tr[i])-t;
    }
    memset(c,0,sizeof c);
    sort(p+1,p+k+1,cmp);
    res=1ll*n*(n-1)/2;
    For(i,1,k){
        int u=p[i];
        res-=ask(l[u],r[u]);
        add(r[u],1);
    }
    //printf("chk %.8Lf %lld\n",rd,res);
    return res;
}

int main()
{
//  freopen("my.out","w",stdout);
    n=read();long long kk;cin>>kk;
    For(i,1,n)cin>>a[i]>>b[i];
    double l=0,r=20000;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)>=kk)r=mid;
        else l=mid;
    }
    printf("%.8lf\n",l);
    return 0;
}