QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800159#9576. Ordainer of Inexorable JudgmentAndyqian7WA 0ms4228kbC++202.7kb2024-12-05 22:38:482024-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:50]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 4228kb
  • [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'