QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#800159 | #9576. Ordainer of Inexorable Judgment | Andyqian7 | WA | 0ms | 4228kb | C++20 | 2.7kb | 2024-12-05 22:38:48 | 2024-12-05 22:38:50 |
Judging History
This is the latest submission verdict.
- [2024-12-23 14:23:26]
- hack成功,自动添加数据
- (/hack/1303)
- [2024-12-06 11:32:56]
- hack成功,自动添加数据
- (/hack/1271)
- [2024-12-05 22:38:48]
- Submitted
answer
#include <bits/stdc++.h>
#define db double
#define pii pair<int, int>
#define rep(i, s, e) for (int i = s; i <= e; i++)
using namespace std;
const db pi = 3.141592653589793, eps = 1e-9;
int main()
{
int n, x0, y0, d, t;
cin >> n >> x0 >> y0 >> d >> t;
vector<pii> v;
rep(i, 1, n)
{
int x, y;
cin >> x >> y;
v.push_back({x, y});
}
v.push_back(v[0]);
v.push_back(v[1]);
auto ang = [](db x, db y)
{
return y >= 0 ? acos(x / sqrt(x * x + y * y)) : acos(x / sqrt(x * x + y * y)) + pi;
};
int per = t / (2 * pi);
db res = t - per * 2 * pi;
db dis = 1e9, x1, y1;
rep(i, 1, n)
{
auto [x, y] = v[i];
auto [x2, y2] = v[i + 1];
auto check = [&](db l)
{
db x1 = x * l + x2 * (1 - l);
db y1 = y * l + y2 * (1 - l);
return x1 * x1 + y1 * y1;
};
db L = 0, R = 1;
while (R - L > eps)
{
db mid1 = (2 * L + R) / 3, mid2 = (L + 2 * R) / 3;
if (check(mid1) < check(mid2))
{
R = mid2;
}
else
{
L = mid1;
}
}
if (check(L) < dis)
{
x1 = x * L + x2 * (1 - L);
y1 = y * L + y2 * (1 - L);
dis = check(L);
}
}
db fa = ang(x1, y1), st = ang(x0, y0);
auto intersect = [&](db theta) { // xsin-ycos=0
bool has1 = 0, has2 = 0;
for (auto [x, y] : v)
{
if (x * sin(theta) > y * cos(theta))
has1 = 1;
if (x * sin(theta) < y * cos(theta))
has2 = 1;
if (fabs(x * sin(theta) - y * cos(theta)) <= d)
return true;
}
return has1 && has2;
};
db L = fa, R = fa + pi / 2;
while (R - L > eps)
{
db mid = (L + R) / 2;
if (intersect(mid))
L = mid;
else
R = mid;
}
db hi = L;
L = fa - pi / 2, R = fa;
while (R - L > eps)
{
db mid = (L + R) / 2;
if (intersect(mid))
R = mid;
else
L = mid;
}
db lo = L;
while (lo < st)
{
lo += 2 * pi, hi += 2 * pi;
}
lo -= st, hi -= st;
db ans = per * (hi - lo);
if (hi > 2 * pi)
{
ans += min(res, hi - 2 * pi);
if (res > lo)
ans += res - lo;
}
else
{
if (res > lo)
{
if (res > hi)
ans += hi - lo;
else
ans += res - lo;
}
}
cout << fixed << setprecision(9) << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4200kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.570796326
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.707752257
result:
ok found '2500.7077523', expected '2500.7077523', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.384241282
result:
ok found '0.3842413', expected '0.3842413', error '0.0000000'
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 4200kb
input:
3 -10000 -10000 10000 10000 -10000 -9999 -10000 -10000 -9999 -10000
output:
4999.844707014
result:
wrong answer 1st numbers differ - expected: '2500.2406700', found: '4999.8447070', error = '0.9997454'