QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#882338#9808. Fragile PinballUESTC_NLNSWA 1ms3968kbC++202.7kb2025-02-05 00:14:472025-02-05 00:14:48

Judging History

This is the latest submission verdict.

  • [2025-02-05 00:14:48]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3968kb
  • [2025-02-05 00:14:47]
  • Submitted

answer

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using ldb = long double;
struct point {
    ldb x, y;
    point operator+(const point& o) const { return {x + o.x, y + o.y}; }
    point operator-(const point& o) const { return {x - o.x, y - o.y}; }
    point operator*(const ldb& o) const { return {x * o, y * o}; }

    ldb operator^(const point& o) const { return x * o.y - o.x * y; }
    ldb operator*(const point& o) const { return x * o.x + o.y * y; }
};
struct seg {
    point a, b;
    void norm() {
        if ((a ^ b) < 0) swap(a, b);
    }
};

point fs(const point& a, const point& b, const point& p) {
    auto v = b - a;
    auto q = a + v * ((p - a) * v / (v * v));
    return q * 2 - p;
}

seg fs(const seg& a, const seg& p) {
    auto p1 = fs(a.a, a.b, p.a);
    auto p2 = fs(a.a, a.b, p.b);
    auto ans = seg{p1, p2};
    ans.norm();
    return ans;
}

point inter(const point& p, const seg& a) {
    auto v = a.a - a.b;
    auto v1 = p ^ v;
    auto v2 = (a.b ^ v);
    return p * (v2 / v1);
}
bool in(const seg& a, const point& b) {
    if (a.a * b < 0 || a.b * b < 0) return 0;

    ldb p1 = (a.a ^ b);
    ldb p2 = (a.b ^ b);
    if (p1 == 0 || p2 == 0) return 1;
    return (p1 > 0) ^ (p2 > 0);
}
void cmx(ldb& a, ldb b) { a = max(a, b); }
int main() {
    int n;
    cin >> n;
    vector<point> a(n);
    vector<ldb> ans(n + 10);
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < n; ++i) {
        auto p = a[i];
        for (auto& u : a) u = u - p;
        vector<seg> s(n);

        for (int i = 0; i < n; ++i) s[i] = {a[i], a[i == n - 1 ? 0 : i + 1]}, s[i].norm();
        for (int j = 0; j < n; ++j) {
            seg range = s[j];
            vector<seg> stk;
            stk.push_back(s[j]);
            auto dfs = [&](auto self, seg rng) -> void {
                cmx(ans[stk.size()], rng.a * rng.a);
                cmx(ans[stk.size()], rng.b * rng.b);
                if (stk.size() == n + 1) return;
                for (int i = 0; i < n; ++i) {
                    seg tmp = s[i];
                    for (const auto& u : stk) tmp = fs(u, tmp);
                    seg nrng;
                    nrng.a = in(rng, tmp.a) ? tmp.a : inter(rng.a, tmp);
                    nrng.b = in(rng, tmp.b) ? tmp.b : inter(rng.b, tmp);
                    if (!in(tmp, nrng.a) || !in(tmp, nrng.b)) continue;
                    stk.push_back(tmp);
                    self(self, nrng);
                    stk.pop_back();
                }
            };
            dfs(dfs, range);
        }
    }
    for (int i = 1; i <= n + 1; ++i) printf("%.8LF\n", sqrtl(ans[i]));
}
/*
3
4 0
0 3
0 2

3
4 0
0 3
0 2

3
4 0
0 3
0 -1

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

3
4 0
0 3
0 -1

output:

5.00000000
8.00000000
8.86818504
12.21002481

result:

ok 4 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

3
4 0
0 3
0 2

output:

5.00000000
5.36656315
6.11191914
6.78220330

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

3
4 0
0 3
0 1

output:

5.00000000
6.18465844
7.19522354
8.65343950

result:

ok 4 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

3
62 -12
-48 100
-45 -96

output:

196.02295784
312.04173783
326.27847772
452.80712373

result:

ok 4 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

3
90 99
-76 -57
99 84

output:

227.79815627
274.35230646
306.89177948
330.10518555

result:

ok 4 numbers

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3968kb

input:

3
-67 22
-86 12
-81 -12

output:

36.76955262
39.56397501
50.91685592
72.35921741

result:

wrong answer 4th numbers differ - expected: '72.2775855', found: '72.3592174', error = '0.0011294'