QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305083 | #7783. Military Maneuver | ucup-team2000 | WA | 0ms | 3900kb | C++23 | 2.7kb | 2024-01-14 17:07:55 | 2024-01-14 17:07:56 |
Judging History
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'