QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735477 | #9576. Ordainer of Inexorable Judgment | .5 ulp (Maxim Plyushkin, Egor Belousov, Maxim Inyutin) | WA | 1ms | 4284kb | C++20 | 2.3kb | 2024-11-11 20:16:07 | 2024-11-11 20:16:08 |
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-11-14 21:58:28]
- hack成功,自动添加数据
- (/hack/1181)
- [2024-11-11 20:16:07]
- Submitted
answer
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
using fp = long double;
using point = array<fp, 2>;
constexpr fp pi = acos((fp)-1);
point operator-(point a, point b) { return {a[0] - b[0], a[1] - b[1]}; }
fp operator&(point a, point b) { return a[0] * b[0] + a[1] * b[1]; }
fp operator^(point a, point b) { return a[0] * b[1] - a[1] * b[0]; }
point operator*(fp a, point b) { return {a * b[0], a * b[1]}; }
fp operator!(point a) { return sqrt(a & a); }
point operator~(point a) { return 1 / !a * a; }
point polar(point a) { return {!a, atan2(a[1], a[0])}; }
point euclid(point a) { return {a[0] * cos(a[1]), a[0] * sin(a[1])}; }
fp mod(fp a) { return a - 2 * pi * floor(a / 2 / pi); }
bool live[1 << 16];
int main() {
point p0;
int n, d, t;
cin >> n >> p0[0] >> p0[1] >> d >> t;
fp ph0 = polar(p0)[1];
point prv; cin >> prv[0] >> prv[1];
vector<point> v{prv};
for (int i = 1; i <= n; ++i) {
point cur = v[0];
if (i < n) cin >> cur[0] >> cur[1];
auto d = cur - prv, dd = ~d;
fp len = !d;
for (int i = 2; i < len; i += 2) v.push_back(prv - -i * dd);
v.push_back(prv = cur);
}
fp tt = mod(t);
vector<pair<fp, int>> s, ss;
for (int i = -1; auto p: v) {
++i;
auto [r, ph] = polar(p);
auto q = euclid({r, ph - tt});
auto dp = (p & p0) > 0? p ^ ~p0: 1e99;
auto dq = (q & p0) > 0? q ^ ~p0: 1e99;
auto first = mod(ph - ph0 - asin(d / r));
auto last = mod(ph - ph0 + asin(d / r) + 1e-8);
s.push_back({first, i * 2});
s.push_back({last, i * 2 + 1});
bool ip = abs(dp) < d, iq = abs(dq) < d;
if (ip) ss.push_back({0, i * 2});
if (!iq || ip && dp > dq) ss.push_back({last, i * 2 + 1});
if (!ip || iq && dp > dq) ss.push_back({first, i * 2});
if (iq) ss.push_back({mod(tt + 1e-8), i * 2 + 1});
}
auto calc = [](auto& s) {
sort(s.begin(), s.end());
fill(live, end(live), 0);
fp res = 0, prv = 0;
int clive = 0;
for (auto t: {0, 1})
for (auto& [x, i]: s) {
if (t && clive) res += mod(x - prv);
prv = x;
clive -= live[i / 2];
live[i / 2] = ~i & 1;
clive += live[i / 2];
}
return res;
};
cout.precision(20);
cout << calc(ss) + calc(s) * round((t - tt) / 2 / pi);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4032kb
input:
3 1 0 1 1 1 2 2 1 2 2
output:
1.00000001
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4284kb
input:
3 1 0 1 2 1 2 2 1 2 2
output:
1.5707963367948966192
result:
ok found '1.5707963', expected '1.5707963', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4220kb
input:
3 1 0 1 10000 1 2 2 1 2 2
output:
2500.7077681774754179
result:
ok found '2500.7077682', expected '2500.7077523', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 4240kb
input:
3 10000 10000 1 10000 10000 9999 10000 10000 9999 10000
output:
0.38425722029026473429
result:
wrong answer 1st numbers differ - expected: '0.3842413', found: '0.3842572', error = '0.0000159'