CF1446F - Line Distance

Posted on Edited on In

CF1446F - Line Distance

题目大意

给定 \(n\) 个点 \(P_i\) ，在每个点对之间连一条线 \(P_iP_j\)

求所有线到原点距离的第 \(k\) 小


分析

这个 \(k\) 大问题的 \(k\) 是 \(O(n^2)\) 级的，因此不是调整，可以考虑二分答案 \(L\)

考虑如何确定 \(d(O,P_iP_j)>L\) ，容易发现这等价于

\(P_iP_j\) 与圆 \(C:x^2+y^2=L^2\) 无交

假设当前确定了 \(P_i\) ，考虑什么时候 \(P_j\) 是合法的

img1

灰色线是切线，用蓝色区域标出了 \(d(O,P_iP_j)>L\) 的范围

直接统计蓝色区域的点并不容易，考虑对于这些点也作切线

Snipaste_2021-05-23_11-40-50.png

容易发现这些点的两个切点恰好被 \(P_i\) 的两个切点分隔开

通过求切点角度，转化为二维区间问题，用树状数组解决

复杂度为 \(O(n\log n\log x)\) ，其中 \(x\) 为精度范围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int N=2e5+10,INF=1e9+10;
const db eps=1e-7,PI=acos((db)-1);

int n; ll m;
int X[N],Y[N];
struct Node{
	db x,y;
	bool operator < (const Node __) const {
		return x<__.x;
	}
} A[N];
db H[N];
int C,HC;

struct BIT{
	int s[N],n;
	void Init(int m){ n=m,memset(s,0,(n+1)<<2); }
	void Add(int p,int x){
		while(p<=n) s[p]+=x,p+=p&-p;
	}
	int Que(int p){
		int res=0;
		while(p) res+=s[p],p-=p&-p;
		return res;
	}
} T;

db norm(db x){
	if(x<0) x+=2*PI;
	if(x>=2*PI) x-=2*PI;
	return x;
}
ll Calc(db L) {
	C=HC=0;
	rep(i,1,n) {
		db D=sqrt(X[i]*X[i]+Y[i]*Y[i]);
		if(L>=D) continue;
		db x=atan2(Y[i],X[i]),y=acos(L/D);
		db l=norm(x-y),r=norm(x+y);
		if(l>r) swap(l,r);
		A[++C]=(Node){l,r};
		H[++HC]=l,H[++HC]=r;
	}
	sort(H+1,H+HC+1);
	ll ans=1ll*n*(n-1)/2;
	sort(A+1,A+C+1),T.Init(HC);
	rep(i,1,C) {
		A[i].x=lower_bound(H+1,H+HC+1,A[i].x)-H;
		A[i].y=lower_bound(H+1,H+HC+1,A[i].y)-H;
		ans-=T.Que(A[i].y)-T.Que(A[i].x);
		T.Add(A[i].y,1);
	}
	return ans;
}

int main(){
	n=rd(),m=rd<ll>();
	rep(i,1,n) X[i]=rd(),Y[i]=rd();
	db l=eps,r=2e4;
	while(r>l*(1+eps)) {
		db mid=(l+r)/2;
		if(Calc(mid)<m) l=mid;
		else r=mid;
	}
	printf("%.10lf\n",l);
}