QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#737949#9576. Ordainer of Inexorable Judgmentlqh2024WA 0ms4176kbC++204.3kb2024-11-12 17:15:182024-11-12 17:15:19

Judging History

你现在查看的是最新测评结果

  • [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-12 17:15:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4176kb
  • [2024-11-12 17:15:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using f64 = long double;

template <class T, class ... A>
void debug(T t, A ... a) {
    cerr << "[" << t;
    ((cerr << ", " << a), ...);
    cerr << "]\n";
}

template <class T = f64>
struct point {
    T x, y;
    static constexpr T pi = acos(T(-1));
    point(T x = {}, T y = {}) : x(x), y(y) {}

    point operator - () const {
        return point(-x, -y);
    }

    T operator * (const point & t) const {
        return x * t.y - y * t.x;
    }
    T operator / (const point & t) const {
        return x * t.x + y * t.y;
    }
    point operator + (const point & t) const {
        return point(*this) += t;
    }
    point operator - (const point & t) const {
        return point(*this) -= t;
    }
    point operator * (const T & t) const {
        return point(*this) *= t;
    }
    point operator / (const T & t) const {
        return point(*this) /= t;
    }

    point & operator += (const point & t) {
        return x += t.x, y += t.y, *this;
    }
    point & operator -= (const point & t) {
        return x -= t.x, y -= t.y, *this;
    }
    point & operator *= (const T & t) {
        return x *= t, y *= t, *this;
    }
    point & operator /= (const T & t) {
        return x /= t, y /= t, *this;
    }

    T square() const { return *this / *this; }
    T len() const { return sqrt(square()); }

    point rotat() const { return point(-y, x); }
    point rotat(const T & t) const {
        return point(x * cos(t) - y * sin(t), y * cos(t) + x * sin(t));
    }
    T theta(T t = 0) const {
        // return ((t = atan2(y, x)) < 0) * 2 * pi + t;
        return (y < 0) * 2 * pi + atan2(y, x);
    }

    struct line {
        point a, b;
        line(point a = {}, point b = {}) : a(a), b(b) {}

        point v() const { return b - a; }
        T P_pos(const point & t) const {
            return (t - a) * v();
        }
        T L_pos(const point & t) const {
            return t.v() * v();
        }
        point L_inter(const line & t) const {
            return a + v() * (t.P_pos(a) / L_pos(t));
        }
    };

    struct circle {
        point o;
        T r;
        circle(point o = {}, T r = {}) : o(o), r(r) {}

        deque<line> tangents(const point & t) const {
            auto v = o - t;
            if (v.square() < r * r) return {};
            if (v.square() == r * r) return {{t, t + v.rotat()}};
            T ang = asin(r / v.len());
            return {{t, t + v.rotat(-ang)}, {t, t + v.rotat(ang)}};
        }
    };
    
};

using line = point<>::line;
using circle = point<>::circle;
constexpr f64 PI = point<>::pi;

void QAQ() {
    int n;
    f64 x0, y0, d, t;
    cin >> n >> x0 >> y0 >> d >> t;

    vector<point<>> a(n + 1);
    circle cir({0, 0}, d);

    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    f64 mx = 0, mn = 1e9;
    for (int i = 1; i <= n; i++) {
        auto tmp = cir.tangents(a[i]);
        auto l1 = tmp[0], l2 = tmp[1];
        mx = max({mx, (-l1.v()).theta(), (-l2.v()).theta()});
        mn = min({mn, (-l1.v()).theta(), (-l2.v()).theta()});
    }
    if (mx >= 3 * PI / 2 && mn <= PI / 2) {
        for (int i = 1; i <= n; i++) {
            a[i] = a[i].rotat().rotat();
        }
        point tmp(x0, y0);
        tmp = tmp.rotat().rotat();
        x0 = tmp.x, y0 = tmp.y;
        mx = 0, mn = 1e9;
        for (int i = 1; i <= n; i++) {
            auto tmp = cir.tangents(a[i]);
            auto l1 = tmp[0], l2 = tmp[1];
            mx = max({mx, (-l1.v()).theta(), (-l2.v()).theta()});
            mn = min({mn, (-l1.v()).theta(), (-l2.v()).theta()});
        }
    }

    auto get = [&](f64 t) {
        f64 cnt = floor(t / (2 * PI)), res = 0;
        t -= cnt * (2 * PI);
        if (mx - mn >= PI) {
            res += cnt * (2 * PI - mx + mn);
            res += min(mn, t);
        } else {
            res += cnt * (mx - mn);
            res += max<double>(0, min(mx, t) - mn);
        }
        return res;
    };

    // debug(mx, mn, 3 * PI / 2, f1, f4);

    cout << get(point<>(x0, y0).theta() + t) - get(point<>(x0, y0).theta()) << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4116kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.570796326795

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4168kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257475

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.384241300290

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 4176kb

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

0.159107955265

result:

wrong answer 1st numbers differ - expected: '2500.2406700', found: '0.1591080', error = '0.9999364'