QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505890#9103. Zayin and FireballWorldFinalEscapedWA 4754ms3880kbC++143.2kb2024-08-05 13:02:552024-08-05 13:02:55

Judging History

你现在查看的是测评时间为 2024-08-05 13:02:55 的历史记录

  • [2024-09-23 15:04:24]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:8ms
  • 内存:3936kb
  • [2024-08-05 13:02:55]
  • 评测
  • 测评结果:100
  • 用时:4754ms
  • 内存:3880kb
  • [2024-08-05 13:02:55]
  • 提交

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