QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#505885 | #9103. Zayin and Fireball | WorldFinalEscaped | TL | 22ms | 3832kb | C++14 | 3.1kb | 2024-08-05 12:59:01 | 2024-09-23 15:04:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const double eps = 1e-9;
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;
}
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
*/
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 3832kb
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.4247779161 9.4247778694 11.1633041138 3.9579337144 18.8495557241 28.2743336259 36.2960451648 28.2743336259 28.2743336259 28.1571366030 417.8318228396 38.2188476544 125660.5645492438 125660.5645492438 125660.5647870612 125660.5647870612 31412.7849419456 39.5793370576 301.2674536253 187...
result:
ok 22 numbers
Test #2:
score: -100
Time Limit Exceeded
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 ...