圣痕[jzoj6496]

发表于 分类于

题意

problem

题解

显然是需要二分半径的。

那么二分完之后，如何判断两个直线的交点是否在圆内呢？

可以求出直线与圆的交点，这两个交点形成了一个扇形。

当且仅当两条直线所代表的扇形出现重合部分，且不是覆盖关系，那么交点即在圆内。

那么将这些交点按极角排序。变成线段上的问题，问在这些线段中选出两个满足上述关系的方案数。

扫描线，然后用一个线段树随便维护。

算出了这个 $r$ 以后，我们需要算距离之和。

因为 $m$ 只有 $10^7$ ，所以对于此时的半径 $r$，暴力在线段树上找出所有的交点计算即可。

此时在圆内的交点个数是比 $m$ 少的（实际上还是有可能大一点的，因为奇奇怪怪的精度问题）。总之，不能统计圆周上的点，因为如果所有的线段交点一样你就完了。不统计圆周上的点可以在极角排序的时候，如果两个点很近，则把右端点排到前面去。

时间复杂度 $O(m+n\log n \log ans)$。

程序

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const db eps=1e-7;
const db pi=acos(-1);
const db inf=1e18;
const int N=4e5+5;
struct line{
	db k,b;
};
struct P{
	db x,y;
};
struct node{
	db x; int y;
};
inline P LineAndCircle(db r,db k,db b)
{
	db a=k*k+1,c=b*b-r*r,t;
	b=b*k*2; t=b*b-4.0*a*c;
	if(t<0) return (P){inf,inf};
	t=sqrt(t);
	return (P){(-b+t)/(a*2),(-b-t)/(a*2)};
}
int flag;
inline bool cmps(const node &A,const node &B)
{
	if(fabs(A.x-B.x)<eps) return A.y<B.y;
	return A.x<B.x;
}
int n,m;
line L[N];

int cnt,in[N<<1],out[N<<1];
node a[N<<1];
inline void build(db k)
{
	P u; cnt=0;
	fo(i,1,n)
	{
		u=LineAndCircle(k,L[i].k,L[i].b);
		if(fabs(u.x-inf)>eps)
		{
			u.x=atan2(L[i].k*u.x+L[i].b,u.x);
			u.y=atan2(L[i].k*u.y+L[i].b,u.y);
			if(u.x>u.y) swap(u.x,u.y);
			a[++cnt]=(node){u.x,i};
			a[++cnt]=(node){u.y,-i};
		}
	}
	sort(a+1,a+cnt+1,cmps);
	fo(i,1,cnt) if(a[i].y>0) in[a[i].y]=i; else out[-a[i].y]=i;
}

vector<int> v[N<<2];
int s[N<<2];
#define lc (u<<1)
#define rc (u<<1|1)
int now;
db sum;
inline void solve(int A,int B)
{
	db x=(L[B].b-L[A].b)/(L[A].k-L[B].k),y=L[A].k*x+L[A].b;
	sum+=sqrt(x*x+y*y);
}
int ask(int u,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		if(flag)
		{
			ff(i,0,v[u].size()) solve(now,v[u][i]);
		}
		return s[u];
	}
	int mid=l+r>>1,ans=0;
	if(L<=mid) ans+=ask(lc,l,mid,L,R);
	if(mid<R)  ans+=ask(rc,mid+1,r,L,R);
	return ans;
}
void add(int u,int l,int r,int p,int x)
{
	s[u]++; if(flag) v[u].pb(x);
	if(l==r) return;
	int mid=l+r>>1;
	(p<=mid)?add(lc,l,mid,p,x):add(rc,mid+1,r,p,x);
}
inline ll calc(db k)
{
	ll ans=0;
	build(k);
	fo(i,0,cnt*4) s[i]=0;
	int l,r;
	fo(i,1,cnt)
		if(a[i].y>0)
		{
			l=in[a[i].y],r=out[a[i].y]; now=a[i].y;
			ans+=ask(1,1,cnt,l,r);
			add(1,1,cnt,r,now);
		}
	return ans;
}
inline db work(db k)
{
	flag=1; ll ans=calc(k);
	return sum-(ans-m)*k;
}
db x,y;
int main()
{
	FO(stigmata);
	n=read(); x=(db)read()/1000.,y=(db)read()/1000.;
	m=read();
	fo(i,1,n)
	{
		L[i].k=(db)read()/1000.,L[i].b=(db)read()/1000.-y;
		L[i].b+=L[i].k*x;
	}
	db l=0,r=1e8,mid;
	fo(t,1,70)
	{
		mid=(l+r)/2.;
		if(calc(mid)>m) r=mid;
		else l=mid;
	}
	cerr<<clock();
	printf("%.10lf",work(r));
	return 0;
}