QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#505889#9103. Zayin and FireballWorldFinalEscapedWA 3ms3864kbC++143.2kb2024-08-05 13:02:372024-08-05 13:02:37

Judging History

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

  • [2024-09-23 15:04:24]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:3ms
  • 内存:4004kb
  • [2024-08-05 13:02:37]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:3864kb
  • [2024-08-05 13:02:37]
  • 提交

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 = 20;
    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: 0
Wrong Answer
time: 3ms
memory: 3864kb

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.4247977788
9.4247657856
11.1632809231
3.9579339565
18.8494732549
28.2742666733
25.1327061153
28.2742666733
28.2742666733
28.1570841484
417.8317827534
38.2188691047
125660.5641265351
125660.5641265351
125660.5643252113
125660.5643252113
31412.7846036305
78.3173000000
301.2674090913
187...

result:

wrong answer 8th numbers differ - expected: '36.29604', found: '25.13271', error = '0.30756'