QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735477#9576. Ordainer of Inexorable Judgment.5 ulp (Maxim Plyushkin, Egor Belousov, Maxim Inyutin)WA 1ms4284kbC++202.3kb2024-11-11 20:16:072024-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:08]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4284kb
  • [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'