QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#734722#9576. Ordainer of Inexorable JudgmentpropaneWA 0ms4400kbC++203.0kb2024-11-11 14:36:302024-11-11 14:36:30

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-11 14:36:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4400kb
  • [2024-11-11 14:36:30]
  • 提交

answer

#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
#include<algorithm>
using namespace std;
using LL = long long;

struct Point{
    double x, y;

    Point operator+(Point t){
        return {x + t.x, y + t.y};
    }

    double operator*(Point t){
        return x * t.x + y * t.y;
    }

    Point operator-(Point t){
        return {x - t.x, y - t.y};
    }

    Point operator*(double a){
        return {x * a, y * a};
    }

    Point operator/(double a){
        return {x / a, y / a};
    }

    double operator^(Point t) {
        return x * t.y - y * t.x;
    }

};

struct line{
    Point p, v;

    Point inter(line a) {
        return p + v * ((a.v ^ (p - a.p)) / (v ^ a.v));
    }

};

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    const double pi = acos(-1), eps = 1e-10;
    int n, x0, y0, d, t;
    cin >> n >> x0 >> y0 >> d >> t;

    // [0, 2pi)
    auto norm = [&](double x){
        while(x < 0) x += 2 * pi;
        while(x >= 2 * pi) x -= 2 * pi;
        return x;
    };

    vector<double> cand;
    vector<Point> p(n);
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        if (x * x + y * y <= d * d){
            cout << t << '\n';
            return 0;
        }
        p[i] = {1.0 * x, 1.0 * y};
        double len = sqrt(x * x + y * y);
        double a = atan2(y, x);
        double cosa = d / len;
        double b = acos(cosa);
        cand.push_back(norm(a - b));
        cand.push_back(norm(a + b));
    }
    cand.push_back(0);
    cand.push_back(2 * pi);
    sort(cand.begin(), cand.end());

    auto check = [&](double a){
        Point v{cos(a), sin(a)};
        for(auto pt : p){
            if (pt * v > -eps and abs(pt ^ v) < d - eps) return true;
        }
        line l1 = {{0, 0}, v};
        for(int i = 0; i < n; i++){
            line l2 = {p[i], (p[(i + 1) % n] - p[i])};
            if (abs(l1.v ^ l2.v) < eps) continue;
            Point o = l1.inter(l2);
            if (o * v > 0 and ((o - p[i]) * (o - p[(i + 1) % n])) < eps) return true;
        }
        return false;
    };


    // [st, st + t]
    double st = norm(atan2(y0, x0));
    int cnt = t / (2 * pi);
    double remain = t - cnt * (2 * pi);
    // [st, st + t]

    auto inter = [&](double l1, double r1, double l2, double r2){
        double l = max(l1, l2);
        double r = min(r1, r2);
        if (l > r) return 0.0;
        return r - l;
    };

    double ans = 0;
    for(int i = 0; i + 1 < cand.size(); i++){
        if (check((cand[i] + cand[i + 1]) / 2)){
            ans += cnt * (cand[i + 1] - cand[i]);
            ans += inter(cand[i], cand[i + 1], st, st + remain);
            ans += inter(cand[i], cand[i + 1], st - 2 * pi, st + remain - 2 * pi);
        }
    }
    cout << fixed << setprecision(20) << ans << '\n';

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.00000000000000000000

result:

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

Test #2:

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

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.57079632679489655800

result:

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

Test #3:

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

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.70775225747547665378

result:

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

Test #4:

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

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.00000000000000000000

result:

wrong answer 1st numbers differ - expected: '0.3842413', found: '0.0000000', error = '0.3842413'