QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882370 | #9808. Fragile Pinball | UESTC_NLNS | WA | 1ms | 3968kb | C++20 | 3.0kb | 2025-02-05 01:06:20 | 2025-02-05 01:06:21 |
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) {
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'