include iostream include vector include iomanip include algorithm usin

 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
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef double ld;
int n, s;
ld z[(int)1e4];
ld r[(int)1e4];
const ld pi = 2 * acosl(0);
inline ld getS(ld zz)
{
ld ans = 10000;
for (int i = 0; i < n; ++i){
if (z[i] - r[i] < zz && zz < z[i] + r[i])
{
ld rr = r[i] * r[i] - (zz - z[i]) * (zz - z[i]);
ans -= pi * rr;
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s;
ld Vsl = 100 * 100 * 100;
for (int i = 0; i < n; ++i){
int x, y, zz, rr;
cin >> rr >> x >> y >> zz;
z[i] = zz / (ld)1000;
r[i] = rr / (ld)1000;
Vsl -= 4 * pi * r[i] * r[i] * r[i] / 3;
}
Vsl /= s;
ld lastZ = 0;
ld curZ = 0;
ld curF = 100 * 100;
ld curV = 0;
const ld roughtStep = (ld)100 / 30000;
for (int i = 0; i + 1 < s; ++i)
{
while (true) {
ld zl = curZ;
ld zr = curZ + roughtStep;
ld zm = curZ + roughtStep / 2;
ld fl = curF;
ld fm = getS(zm);
ld fr = getS(zr);
ld addV = roughtStep * (fl + 4 * fm + fr) / 6;
if (curV + addV < Vsl)
{
curV += addV;
curZ = zr;
curF = fr;
}
else
{
ld l = 0;
ld r = roughtStep;
for (int i = 0; i < 40; ++i)
{
ld m = (l + r) / 2;
ld zl = curZ;
ld zr = curZ + m;
ld zm = curZ + m / 2;
ld fl = curF;
ld fm = getS(zm);
ld fr = getS(zr);
ld addV = m * (fl + 4 * fm + fr) / 6;
if (curV + addV < Vsl) l = m;
else r = m;
}
ld m = (l + r) / 2;
curZ += m;
curF = getS(curZ);
cout << fixed << setprecision(10) << curZ - lastZ << '\n';
lastZ = curZ;
curV = 0;
break;
}
}
}
cout << fixed << setprecision(10) << 100 - curZ << '\n';
return 0;
}