QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#750562#9576. Ordainer of Inexorable JudgmentUESTC_DECAYALI#WA 0ms3968kbC++173.3kb2024-11-15 14:59:022024-11-15 14:59:03

Judging History

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

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-15 14:59:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3968kb
  • [2024-11-15 14:59:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
using LD = long double;

const LD eps = 1e-8;
const LD PI = acosl(-1.0L);

LD sqr(LD x) {return x*x;}
int sgn(LD x) {return fabs(x)<=eps ? 0 : (x>eps ? 1 : -1);}

struct Point {
    LD x, y;
    LD operator^(const Point &b) const {return x*b.y - y*b.x;}
    LD operator*(const Point &b) const {return x*b.x + y*b.y;}
    bool operator<(const Point &b) const {return sgn((*this)^b) > 0;}
    Point operator*(const LD &b) const {return Point{x*b, y*b};}
    Point operator+(const Point &b) const {return Point{x+b.x, y+b.y};}
    Point operator-(const Point &b) const {return Point{x-b.x, y-b.y};}
    LD len() const {return sqrtl(x*x+y*y);}
    LD len2() const {return x*x+y*y;}
    Point rot(const LD &cosr, const LD &sinr) {
        return {x*cosr - y*sinr, x*sinr + y*cosr};
    }
    LD ang(const Point &a) const {
        return atan2l((*this)^a, (*this)*a);
    }
}; 

LD p_seg_dis2(Point p, Point a, Point b) {
    if (sgn((p-a)*(b-a))<=0 && sgn((p-b)*(a-b))<=0) 
        return min((a-p).len2(), (b-p).len2());
    Point v = b-a;
    LD res = abs(v ^ (p-a)) / v.len();
    return sqr(res);
}

struct Circle {
    Point c;
    LD r;

    pair<Point, Point> tangent(const Point &a) const {
        Point e = a-c;
        e = e * (r / e.len());
        const LD costh = r / (c-a).len(), sinth = sqrtl(1 - sqr(costh));
        const Point t1 = c + e.rot(costh, -sinth), t2 = c + e.rot(costh, sinth);
        return {t1, t2};
    }
};

int n, xx0, yy0, d;
LD t;
Circle cir;
vector<Point> conv;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    cin >> n >> xx0 >> yy0 >> d >> t;
    cir = Circle{{0.0L, 0.0L}, (LD)d};
    conv.reserve(n);
    for (int i=0; i<n; ++i) {
        int x, y; cin >> x >> y;
        conv.push_back(Point{(LD)x, (LD)y});
    }

    bool ok = false;
    for (int i=0; i<n; ++i) {
        if (sgn(sqr(d) - p_seg_dis2({0, 0}, conv[i], conv[(i+1)%n])) >= 0) {
            ok = true; break;
        }
    }

    if (ok) {
        cout << t << '\n';
        return 0;
    }

    vector<Point> vt1, vt2;
    for (int i=0; i<n; ++i) {
        auto [t1, t2] = cir.tangent(conv[i]);
        vt1.push_back(t1);
        vt2.push_back(t2);
    }

    auto findmn = [&](vector<Point> &vec){
        auto res = vec[0];
        for (auto p : vec) res = min(res, p);
        return res;
    };
    auto findmx = [&](vector<Point> &vec){
        auto res = vec[0];
        for (auto p : vec) res = max(res, p);
        return res;
    };

    auto t1 = findmx(vt1);
    auto t2 = findmn(vt2);
    auto rt1 = t1.rot(0, 1), rt2 = t2.rot(0, -1);
    LD ang = rt2.ang(rt1);

    LD ans = 0.0L;
    int round = floor(t / (2*PI) + eps);
    ans += round * ang;
    t -= round*2*PI;

    Point v = Point{xx0, yy0};
    LD th2 = v.ang(rt2); if (sgn(th2) < 0) th2 = 2*PI+th2;
    LD th1 = v.ang(rt1); if (sgn(th1) < 0) th1 = 2*PI+th1;
    // printf("th2=%Lf th1=%Lf\n", th2, th1);

    if (sgn(rt2^v)>0 && sgn(v^rt1)>0) {
        if (t < th2) ans += t;
        else ans += th2 + (t > th1 ? t-th1 : 0);
    } else ans += min(th1, t) - th2;
    cout << ans << '\n';
    return 0;
}

詳細信息

Test #1:

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

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: 3912kb

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: 3856kb

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: -100
Wrong Answer
time: 0ms
memory: 3968kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

3.836296860854

result:

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