QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305083#7783. Military Maneuverucup-team2000WA 0ms3900kbC++232.7kb2024-01-14 17:07:552024-01-14 17:07:56

Judging History

你现在查看的是最新测评结果

  • [2024-01-14 17:07:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3900kb
  • [2024-01-14 17:07:55]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#ifdef ONLINE_JUDGE
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>

// #define double long double
struct simpson {
    double area(double l, double r, double fl, double fm, double fr) {
        return (fl + 4 * fm + fr) * (r - l) / 6;
    }
    double solve(double (*f)(double), double l, double m, double r, double eps,
                 double fl, double fm, double fr, double a) {
        double lm = (l + m) / 2, rm = (m + r) / 2;
        double flm = f(lm), frm = f(rm);
        double left = area(l, m, fl, flm, fm), right = area(m, r, fm, frm, fr);
        if (fabs(left + right - a) <= 15 * eps)
            return left + right + (left + right - a) / 15.0;
        return solve(f, l, lm, m, eps / 2, fl, flm, fm, left) +
               solve(f, m, rm, r, eps / 2, fm, frm, fr, right);
    }
    double solve(double (*f)(double), double l, double r, double eps) {
        double m = (l + r) / 2;
        double fl = f(l), fm = f(m), fr = f(r);
        return solve(f, l, m, r, eps, fl, fm, fr, area(l, r, fl, fm, fr));
    }
} _simpson;

const double EPS = 3E-8;
const int SIZE = 20;
const double PI = acos(-1);
long long XL, YL, XR, YR;
int N;
std::pair<long long, long long> P[3000];
double XX[3000];

double ff(double y) {
    double val0 = XX[0] + (P[0].second - y) * (P[0].second - y);
    double min = val0, max = val0;
    for (int i = 1; i < N; ++i) {
        double val = XX[i] + (P[i].second - y) * (P[i].second - y);
        if (min > val) min = val;
        if (max < val) max = val;
    }
    return max - min;
}

double f(double x) {
    static int cnt = 0;
    for (int i = 0; i < N; ++i)
        XX[i] = P[i].first - x, XX[i] *= XX[i];
    double area = 0;
    for (int t = 0; t < SIZE; ++t) {
        area += (YR - YL) * ff((YL * (t + .5) + YR * (SIZE - .5 - t)) / SIZE);
    }
    area /= SIZE;
    double ret = _simpson.solve(ff, YL, YR, std::max(EPS, area * EPS) / (1ll << 12));
    printf("%d %.10lf %.10lf\n", ++cnt, x, ret);
    return ret;
}

int main() {
    scanf("%lld%lld%lld%lld", &XL, &YL, &XR, &YR);
    // XL = YL = -10000, XR = YR = 10000;
    scanf("%d", &N);
    // N = 2000;
    for (int i = 0; i < N; ++i) {
        scanf("%lld%lld", &P[i].first, &P[i].second);
        // X[i] = rand() % 20000 - 10000; Y[i] = rand() % 20000 - 10000;
    }
    std::sort(P, P + N);
    double area = 0;
    for (int t = 0; t < SIZE; ++t) {
        area += (XR - XL) * f((XL * (t + .5) + XR * (SIZE - .5 - t)) / SIZE);
    }
    area /= SIZE;
    printf("%.10lf\n", _simpson.solve(f, XL, XR, std::max(EPS, area * EPS)) *
                           PI / (XR - XL) / (YR - YL));
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3900kb

input:

0 0 2 2
2
3 1
1 3

output:

1 1.9500000000 7.6100000000
2 1.8500000000 6.8900000000
3 1.7500000000 6.2500000000
4 1.6500000000 5.6900000000
5 1.5500000000 5.2100000000
6 1.4500000000 4.8100000000
7 1.3500000000 4.4900000000
8 1.2500000000 4.2500000000
9 1.1500000000 4.0900000000
10 1.0500000000 4.0100000000
11 0.9500000000 4.0...

result:

wrong answer 1st numbers differ - expected: '8.3775804', found: '1.0000000', error = '0.8806338'