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
| #include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e3 + 5;
using db = double;
using pdi = pair<db, int>;
const db eps = 1e-8, pi = acos(-1.0);
int sgn(db x) { return (x<-eps ? -1 : x>eps); }
db sqr(db x) { return x*x; }
int n, s;
db R;
struct P
{
db x, y;
P() {}
db dis(P p) { return sqrt(sqr(x-p.x) + sqr(y-p.y)); }
}p[N];
void norm(db& theta)
{
if(sgn(theta)<0) theta += 2*pi;
}
bool check(db r)
{
for(int i=1; i<=n; i++)
{
vector<pdi> pre;
int cnt = 0;
for(int j=1; j<=n; j++)
{
db d = p[i].dis(p[j]);
if(sgn(d)==0) { ++cnt; continue; }
if(sgn(d-2*r)>=0) continue;
db p1 = atan2(p[j].y-p[i].y, p[j].x-p[i].x);
db p2 = acos(0.5*d/r);
db l = p1 - p2, r = p1 + p2;
norm(l), norm(r);
if(sgn(r-l)>=0) pre.push_back({l, 1}), pre.push_back({r+eps, -1});
else
{
pre.push_back({0, 1}), pre.push_back({r+eps, -1});
pre.push_back({l, 1}), pre.push_back({2*pi+eps, -1});
}
}
int mx = cnt, cur = cnt;
sort(begin(pre), end(pre));
for(int i=0; i<(int)pre.size(); i++)
{
cur += pre[i].se;
if(cur>mx) mx = cur;
}
if(mx>=s) return true;
}
return false;
}
db work()
{
db l = 0.0, r = 0.0;
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
r = max(r, p[i].dis(p[j]));
db ans = 0.0;
while(r-l>eps)
{
db mid = (l+r)/2;
if(check(mid)) r = mid, ans = mid;
else l = mid;
}
return ans + R;
}
void solve()
{
cin >> n >> s;
for(int i=1; i<=n; i++) cin >> p[i].x >> p[i].y;
cin >> R;
if(s>n) cout << "The cake is a lie.\n";
else cout << work() << '\n';
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(4);
int _; cin >> _;
while(_--) solve();
return 0;
}
|