QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882370#9808. Fragile PinballUESTC_NLNSWA 1ms3968kbC++203.0kb2025-02-05 01:06:202025-02-05 01:06:21

Judging History

This is the latest submission verdict.

  • [2025-02-05 01:06:21]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3968kb
  • [2025-02-05 01:06:20]
  • 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);
}
const ldb eps = 1e-12;
bool in(const seg& a, const point& b) {
    // if (a.a * b < eps || a.b * b < eps) return 0;

    ldb p1 = (a.a ^ b);
    ldb p2 = (a.b ^ b);
    if (abs(p1) <= eps || abs(p2) <= eps) return 1;
    return (p1 > eps) && (p2 < -eps);
}

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) {
            vector<int> vis(n);
            seg range = s[j];
            vector<seg> stk;
            vis[j] = 1;
            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) {
                    if (stk.size() != n && vis[i]) continue;
                    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);
                    vis[i] = 1;
                    self(self, nrng);
                    stk.pop_back();
                    vis[i] = 0;
                }
            };
            dfs(dfs, range);
        }
    }
    for (int i = 1; i <= n + 1; ++i) printf("%.20LF\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

3
-67 22
-86 12
-81 -12

3
14 34
-5 24
0 0

3
4 0
0 3
0 2
*/

詳細信息

Test #1:

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

input:

3
4 0
0 3
0 -1

output:

5.00000000000000000000
8.00000000000000000000
8.86818503879756340601
12.21002481088195582796

result:

ok 4 numbers

Test #2:

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

input:

3
4 0
0 3
0 2

output:

5.00000000000000000000
5.36656314599949527165
6.11191913849942517010
6.78220330441662831722

result:

ok 4 numbers

Test #3:

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

input:

3
4 0
0 3
0 1

output:

5.00000000000000000000
6.18465843842649082469
7.19522354274454488095
8.65343949929425340292

result:

ok 4 numbers

Test #4:

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

input:

3
62 -12
-48 100
-45 -96

output:

196.02295783912658835857
312.04173783276056028391
326.27847771877617752412
452.80712372911078525406

result:

ok 4 numbers

Test #5:

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

input:

3
90 99
-76 -57
99 84

output:

227.79815626997510885632
274.35230645776344954312
306.89177947709210378391
330.10518554643359473433

result:

ok 4 numbers

Test #6:

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

input:

3
-67 22
-86 12
-81 -12

output:

36.76955262170047127046
39.56397500565403616349
50.91685591710600820164
72.27758551745063939770

result:

ok 4 numbers

Test #7:

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

input:

3
71 -48
-81 2
-83 -44

output:

160.01249951175689324734
308.05679456756879494583
308.05679456756879494583
308.05679456756879500134

result:

ok 4 numbers

Test #8:

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

input:

3
44 -44
-31 -77
8 -98

output:

81.93900170248597799455
115.79266829979315253651
125.60604402992012824936
167.93649349697933648162

result:

ok 4 numbers

Test #9:

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

input:

3
40 91
-42 90
-5 -99

output:

195.25624189766635985244
378.87426679199884818616
378.87426679199884818616
378.87426679199884818616

result:

ok 4 numbers

Test #10:

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

input:

4
-10 -97
13 -98
90 50
42 97

output:

200.84820138602187641896
269.68734146533457932127
382.16606804049615697672
476.59926283039679295594
529.68357243354577812422

result:

wrong answer 5th numbers differ - expected: '476.5992628', found: '529.6835724', error = '0.1113814'