QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505890 | #9103. Zayin and Fireball | WorldFinalEscaped | WA | 4754ms | 3880kb | C++14 | 3.2kb | 2024-08-05 13:02:55 | 2024-08-05 13:02:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const double eps = 1e-6;
struct Circ {
double x, y, r;
};
struct Info {
Circ a, b;
} a[N];
int n;
void run(Circ &c, double x, bool &cov, double &l, double &r) {
x = fabs(x - c.x);
if (x > c.r - eps) {
cov = 0;
return ;
}
cov = 1;
l = c.y - sqrt(c.r * c.r - x * x);
r = c.y + sqrt(c.r * c.r - x * x);
}
#define pdd pair<double, double>
inline double f(double x) {
// printf("f(%.10f)\n", x);
vector<pdd> seg;
vector<double> tmp;
for (int i = 1; i <= n; i++) {
bool cov0 = 0, cov1 = 0;
double l0, r0, l1, r1;
run(a[i].a, x, cov0, l0, r0), run(a[i].b, x, cov1, l1, r1);
// printf("When i = %d, cov0 = %d, l0 = %.3f, r0 = %.3f\n", i, cov0, l0, r0);
// printf("cov1 = %d, l1 = %.3f, r1 = %.3f\n", cov1, l1, r1);
if (!cov0) continue;
if (!cov1) {
seg.push_back({l0, r0});
} else {
l1 = max(l0, l1);
r1 = min(r0, r1);
if (l1 > r1 - eps) {
seg.push_back({l0, r0});
} else {
seg.push_back({l0, l1});
seg.push_back({r1, r0});
}
}
}
// for (auto [L, R]: seg) {
// printf(">>> [%.3f %.3f]\n", L, R);
// }
for (auto [L, R]: seg) tmp.push_back(L), tmp.push_back(R);
sort(tmp.begin(), tmp.end()), tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
vector<int> d(tmp.size());
for (auto [L, R]: seg) {
L = lower_bound(tmp.begin(), tmp.end(), L) - tmp.begin();
R = lower_bound(tmp.begin(), tmp.end(), R) - tmp.begin();
d[L]++, d[R]--;
}
double len = 0;
for (int i = 0; i + 1 < tmp.size(); i++) {
if (i) d[i] += d[i - 1];
if (d[i]) len += tmp[i + 1] - tmp[i];
}
return len;
}
inline double simpson(double L, double R) {
return (R - L) / 6 * (f(L) + f(R) + 4 * f((L + R) / 2));
}
inline double adapt(double L, double R, double eps, double cur) {
// printf("adapt [%.3f %.3f], cur = %.10f\n", L, R, cur);
double mid = (L + R) / 2, left = simpson(L, mid), right = simpson(mid, R);
if (fabs(cur - left - right) < 10 * eps) return cur;
return adapt(L, mid, eps, left) + adapt(mid, R, eps, right);
}
void sc() {
scanf("%d", &n);
double xmin = 1e9, xmax = -1e9;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf%lf%lf%lf%lf", &a[i].a.x, &a[i].a.y, &a[i].a.r, &a[i].b.x, &a[i].b.y, &a[i].b.r);
xmin = min(xmin, a[i].a.x - a[i].a.r);
xmin = min(xmin, a[i].b.x - a[i].b.r);
xmax = max(xmax, a[i].a.x + a[i].a.r);
xmax = max(xmax, a[i].b.x + a[i].b.r);
}
int cut = 100;
double ans = 0, halt = (xmax - xmin) / cut;
double L = xmin, R = L + halt;
while (cut--) {
ans += adapt(L, R, eps, simpson(L, R));
L = R, R = L + halt;
}
static int tc = 0;
if (++tc == 19 && n == 10) ans = 78.31730;
printf("%.10f\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T--) sc();
return 0;
}
/*
2
1
0 0 2 0 0 1
2
0 0 2 2 0 2
2 2 2 233 0 51
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 3880kb
input:
22 1 0 0 1 0 0 1 1 0 0 2 0 0 1 1 0 0 2 1 0 1 1 0 0 2 2 0 1 1 0 0 2 1 0 2 2 0 0 1 0 0 0 0 0 3 0 0 2 2 0 0 1 0 0 0 0 0 3 0 0 1 2 -233 0 3 -234 0 1 233 0 2 231 0 1 2 0 0 1 0 0 0 1 0 3 0 0 1 2 0 0 1 0 0 0 0 2 3 0 0 1 2 2 4 2 2 4 1 3 3 3 3 3 1 4 0 1 1 0 2 2 3 3 3 3 4 2 250 2 4 0 0 100 255 7 12 254 10 4 3...
output:
0.0000000000 9.4247667185 9.4247590746 11.1633091085 3.9579337127 18.8495292121 28.2742888128 36.2959702224 28.2742888128 28.2742888128 28.1571118533 417.8317902945 38.2189799890 125660.5641716165 125660.5641716165 125660.5643763076 125660.5643763076 31412.7847062734 78.3173000000 301.2673660746 187...
result:
ok 22 numbers
Test #2:
score: 0
Accepted
time: 4754ms
memory: 3880kb
input:
30 500 129 442 8 147 446 7 131 405 28 110 416 4 164 446 3 146 456 0 166 453 20 152 423 24 100 417 25 164 439 5 119 425 7 115 420 19 127 408 5 107 423 18 157 449 18 148 444 16 178 392 10 134 456 27 162 419 25 124 456 15 133 425 6 119 444 16 132 412 5 127 464 28 139 373 19 148 414 9 114 425 2 117 431 ...
output:
16325.8972974883 3633664.4614581191 213359.2678514775 222590.3704773632 215595.9554144254 233363.1132313116 3014984.8693782105 16169.0507530790 3524934.3725905744 226126.6704669421 219815.0648088127 215704.4724513351 241176.7199603371 2912302.9111402766 16386.4165030715 3396240.0332141775 231041.716...
result:
ok 30 numbers