QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882346 | #9808. Fragile Pinball | UESTC_NLNS | WA | 1ms | 3840kb | C++20 | 2.8kb | 2025-02-05 00:19:05 | 2025-02-05 00:19:06 |
Judging History
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) {
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
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
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: 0ms
memory: 3840kb
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: 1ms
memory: 3840kb
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: 1ms
memory: 3840kb
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: 0ms
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: 3840kb
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'