QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#780034 | #9808. Fragile Pinball | FR | WA | 18ms | 4048kb | C++17 | 5.3kb | 2024-11-24 23:49:57 | 2024-11-24 23:49:58 |
Judging History
answer
#include <bits/stdc++.h>
struct vec
{
double x, y;
double len() const { return hypot(x, y); }
double len2() const;
};
vec operator+(const vec& x, const vec &y) { return {x.x + y.x, x.y + y.y}; }
vec operator-(const vec& x, const vec &y) { return {x.x - y.x, x.y - y.y}; }
double operator*(const vec& x, const vec &y) { return x.x * y.x + x.y * y.y; }
vec operator*(const vec& x, const double &y) { return {x.x * y, x.y * y}; }
vec operator/(const vec& x, const double &y) { return {x.x / y, x.y / y}; }
double det(const vec& x, const vec &y) { return x.x * y.y - x.y * y.x; }
double wedge(const vec& x, const vec &y, const vec &z) { return det(y - x, z - x); }
double area(const vec& x, const vec &y, const vec &z) { return wedge(x, y, z) / 2; }
double vec::len2() const { return *this * *this; }
bool operator==(const vec& x, const vec &y) { return (x - y).len2() < 1E-14; }
bool operator!=(const vec& x, const vec &y) { return (x - y).len2() >= 1E-14; }
vec proj(const vec& dir, const vec &v) { return dir * (dir * v) / dir.len2(); }
vec proj(const vec& x, const vec& y, const vec &p) { return x + proj(y - x, p - x); }
vec refl(const vec& x, const vec& y, const vec &p) { return proj(x, y, p) * 2 - p; }
bool sameray(const vec& x, const vec& y)
{
return std::abs(det(x, y)) <= 1E-10 && x * y >= 0;
}
bool sbtn(const vec& x, const vec& y, const vec &z)
{
if (sameray(x, y) || sameray(y, z))
return false;
if (det(x, y) < -1E-10 && det(y, z) < -1E-10)
return false;
if (det(x, y) < -1E-10 || det(y, z) < -1E-10)
return det(x, z) < 0;
return true;
}
bool projon(const vec& dir, const vec &v)
{
double x = dir * v;
return 1E-10 < x && x < dir.len2() - 1E-10;
}
bool projon(const vec& x, const vec& y, const vec &p) { return projon(y - x, p - x); }
bool onray(const vec& dir, const vec &v)
{
auto p = proj(dir, v);
if (p != v)
return false;
return -1E-10 < dir * v;
}
bool onray(const vec& x, const vec& y, const vec &p)
{
return onray(y - x, p - x);
}
double dist(const vec& x, const vec& y) { return (y - x).len(); }
std::ostream &operator<<(std::ostream &os, const vec &v)
{
return os << "(" << v.x << ", " << v.y << ")";
}
struct v3
{
double x, y, z;
v3(vec v) { x = v.x, y = v.y, z = 1; }
v3() {}
vec norm()
{
return {x / z, y / z};
}
};
v3 cross(const v3 &a, const v3 &b)
{
v3 res;
res.x = a.y * b.z - a.z * b.y;
res.y = a.z * b.x - a.x * b.z;
res.z = a.x * b.y - a.y * b.x;
return res;
}
std::pair<bool, vec> inter(const vec& p1, const vec& p2, const vec& q1, const vec& q2)
{
v3 l1 = cross(v3(p1), v3(p2));
v3 l2 = cross(v3(q1), v3(q2));
v3 res = cross(l1, l2);
if (std::abs(res.z) < 1E-10)
return {false, {}};
return {true, res.norm()};
}
vec getpt(const std::vector<vec> &pts, int i)
{
i %= int(pts.size());
if (i < 0)
i += pts.size();
return pts[i];
}
std::pair<vec, vec> edge(const std::vector<vec> &pts, int i)
{
return {getpt(pts, i), getpt(pts, i + 1)};
}
double Ans[] = {0, 0, 0, 0, 0, 0, 0};
bool vis[7] = {false, false, false, false, false, false, false};
int en[7];
std::vector<vec> poly[7];
int N;
int chk(int i, int j)
{
j %= N;
if (j < 0)
j += N;
if (en[i] != -1 && j == en[i])
return 1;
if (i != 0 && j == en[i - 1])
return -1;
return 0;
}
vec pred(int i, int j);
vec succ(int i, int j);
vec pred(int i, int j)
{
int x = chk(i, j - 1);
return x == 0 ? getpt(poly[i], j - 1) : succ(i + x, j);
}
vec succ(int i, int j)
{
int x = chk(i, j);
return x == 0 ? getpt(poly[i], j + 1) : pred(i + x, j);
}
void calc1(int r, vec x, vec y)
{
// std::cout << "!! " << r << ' ' << N << std::endl;
// std::cout << x << ' ' << y << std::endl;
// for (int i = 0; i <= r; ++i)
// {
// for (int j = 0; j < N; ++j)
// std::cout << poly[i][j] << ' ';
// std::cout << std::endl;
// }
double res = 1E9;
for (int i = 0; i <= r; ++i)
for (int j = 0; j < N; ++j)
if (chk(i, j) == 0)
{
auto [q1, q2] = edge(poly[i], j);
auto [f, p] = inter(x, y, q1, q2);
if (f && projon(q1, q2, p))
res = std::min(res, dist(x, p));
}
for (int i = 0; i <= r; ++i)
for (int j = 0; j < N; ++j)
if (onray(x, y, poly[i][j]))
{
vec q0 = pred(i, j), q1 = poly[i][j], q2 = succ(i, j);
// std::cout << "!! " << q0 << ' ' << q1 << ' ' << q2 << std::endl;
if (i & 1 ? sbtn(q2 - q1, y - x, q0 - q1) : sbtn(q0 - q1, y - x, q2 - q1))
res = std::min(res, dist(x, q1));
}
assert(res < 1E8);
// std::cout << res << std::endl;
// std::cout << std::endl;
Ans[r] = std::max(Ans[r], res);
}
void calc(int r)
{
for (int i = 0; i != N; ++i)
{
vec pt = poly[0][i];
for (int jr = 0; jr <= r; ++jr)
{
for (int j = 0; j < N; ++j)
{
vec y = poly[jr][j];
if (pt == y)
break;
calc1(r, pt, y);
}
}
}
}
void dfs(int r)
{
en[r] = -1;
calc(r);
for (int i = 0; i != N; ++i)
if (!vis[i])
{
en[r] = i;
vis[i] = true;
auto [p1, p2] = edge(poly[r], i);
for (int i = 0; i != N; ++i)
poly[r + 1][i] = refl(p1, p2, poly[r][i]);
dfs(r + 1);
vis[i] = false;
}
en[r] = -1;
}
int main()
{
std::cin >> N;
for (int i = 0; i != 7; ++i)
poly[i].resize(N);
for (auto &pt : poly[0])
std::cin >> pt.x >> pt.y;
dfs(0);
for (int i = 0; i <= N; ++i)
printf("%.14lf\n", Ans[i]);
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4036kb
input:
3 4 0 0 3 0 -1
output:
5.00000000000000 8.00000000000000 8.86818503879756 12.21002481088196
result:
ok 4 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
3 4 0 0 3 0 2
output:
5.00000000000000 5.36656314599950 6.11191913849942 6.78220330441663
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
3 4 0 0 3 0 1
output:
5.00000000000000 6.18465843842649 7.19522354274454 8.65343949929425
result:
ok 4 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
3 62 -12 -48 100 -45 -96
output:
196.02295783912658 312.04173783276053 326.27847771877617 452.80712372911080
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
3 90 99 -76 -57 99 84
output:
227.79815626997510 274.35230645776346 306.89177947709214 330.10518554643352
result:
ok 4 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 -67 22 -86 12 -81 -12
output:
36.76955262170047 39.56397500565404 50.91685591710601 72.27758551745065
result:
ok 4 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
3 71 -48 -81 2 -83 -44
output:
160.01249951175689 308.05679456756883 308.05679456756883 308.05679456756883
result:
ok 4 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
3 44 -44 -31 -77 8 -98
output:
81.93900170248598 115.79266829979316 125.60604402992014 167.93649349697935
result:
ok 4 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
3 40 91 -42 90 -5 -99
output:
195.25624189766637 378.87426679199888 378.87426679199888 378.87426679199888
result:
ok 4 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 4032kb
input:
4 -10 -97 13 -98 90 50 42 97
output:
200.84820138602188 269.68734146533455 382.16606804049610 476.59926283039630 476.59926283039630
result:
ok 5 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
4 39 89 -72 -94 87 -58 90 36
output:
214.03270778084362 413.74414660992380 413.74414660992380 502.96571824848036 595.01821265490548
result:
ok 5 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
4 -6 -90 33 -75 4 97 -36 -69
output:
187.26718879718359 269.54944439736869 309.20805779551495 364.70165807157008 395.37828755440637
result:
ok 5 numbers
Test #13:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
4 44 81 27 81 60 -57 83 3
output:
141.89080308462562 187.12271495993613 251.47668954805476 274.12765684348471 286.31951740573038
result:
ok 5 numbers
Test #14:
score: 0
Accepted
time: 2ms
memory: 3876kb
input:
4 96 -13 99 1 -67 -36 67 -37
output:
170.07351351694948 183.08542624904550 223.21210351724531 277.37918419740191 306.15039727040045
result:
ok 5 numbers
Test #15:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
4 -18 -98 80 -59 73 68 -78 -62
output:
199.25109786397664 378.32587882437446 378.32587882437451 512.61754381185767 557.38745761591031
result:
ok 5 numbers
Test #16:
score: -100
Wrong Answer
time: 18ms
memory: 3984kb
input:
5 -90 41 -93 27 94 79 83 91 -44 94
output:
194.09533739891847 206.35552445442491 256.73130200089082 337.34690346234032 377.92916040834780 377.92916040834780
result:
wrong answer 6th numbers differ - expected: '396.6629387', found: '377.9291604', error = '0.0472285'