QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#754086#9576. Ordainer of Inexorable Judgmentucup-team4906#WA 0ms3904kbC++174.9kb2024-11-16 14:11:482024-11-16 14:11:49

Judging History

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

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

answer

#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int> 

typedef long long ll;
typedef unsigned long long ull;

#define N 110
typedef double T;
typedef double db;
const db pi = acosl(-1);
const db eps = 1e-8;
int sgn(T x) {
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
struct point {
    T x, y; 
    point() {}
    point(T x, T y) : x(x), y(y) {}
    point operator + (point B) const {return point(x + B.x, y + B.y);}
    point operator - (point B) const {return point(x - B.x, y - B.y);}
    point operator * (T k) const {return point(x * k, y * k);}
    point operator / (T k) const {return point(x / k, y / k);}
    bool operator == (point B) const {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    bool operator < (point B) const {return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);}
    T cross(point p) const {return x * p.y - y * p.x;}
    int left(point p) const {return sgn(cross(p));}
    T len() const {return sqrtl(x * x + y * y);}
    point rot(long double cosr, long double sinr) {return point(x * cosr - y * sinr, x * sinr + y * cosr);}
};
T dot(point x) {return x.x * x.x + x.y * x.y;}
db dis(point A, point B) {return sqrtl((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
int get_region(point p) {
    return sgn(p.y) < 0 ? -1 : sgn(p.y) > 0 | (sgn(p.y) == 0 & sgn(p.x) < 0);
}
bool cmp_arg(point a, point b) {
    int p = get_region(a), q = get_region(b);
    if(p != q) return p < q;
    if(a.left(b) == 0) return dot(a) < dot(b);
    return a.left(b) == 1;
} 

int n, x0, Y0, d, t;
point o(0, 0);
pair<point, point> tangent(const point a) {
    point e = a; e = e / e.len() * d;
    long double costh = d / dis(a, o), sinth = sqrtl(1 - costh * costh);
    point t1 = o + e.rot(costh, -sinth), t2 = o + e.rot(costh, sinth); 
    // 两个切点
    return {t1, t2};
}
bool cmp(pair<point, pair<point, int>> x1, pair<point, pair<point, int>> x2) {
    return cmp_arg(x1.first, x2.first);
}
point rotate(point A, T rad) {
    return point(A.x * cosl(rad) - A.y * sinl(rad), A.x * sinl(rad) + A.y * cosl(rad));
}
db dot(point A, point B) {return A.x * B.x + A.y * B.y;}
db len(point A) {return sqrtl(dot(A, A));}
db angle(point A, point B) {
    db tmp = dot(A, B) / len(A) / len(B);
    if(tmp > 1) tmp = 1;
    else if(tmp < -1) tmp = -1;
    db res = acosl(tmp);
    // cout << res << "QAQ\n";
    // cout << A.x << " " << A.y << " " << B.x << " " << B.y << " " << B.left(A) << "????\n";
    if(B.left(A) == 1) res = 2 * pi - res;
    return res;
}

void sol() {
    cout << fixed << setprecision(10);
    cin >> n >> x0 >> Y0 >> d >> t;
    vector<point> p;
    vector<pair<point, pair<point, int>>> qaq;
    F(i, 0, n - 1) {
        int x, y; cin >> x >> y;
        p.push_back(point(x, y));
        auto [u, v] = tangent(point(x, y));
        qaq.push_back({point(x, y) - u, {u, i}}), qaq.push_back({point(x, y) - v, {v, i}});
    }
    sort(qaq.begin(), qaq.end(), cmp);
    point st, ed;
    int cnt = 0;
    for(int i = 0; i < qaq.size(); i ++) if(qaq[i].first.left(qaq[(i + 1) % qaq.size()].first) == -1) {
        cnt ++;
        point u = qaq[(i + 1) % qaq.size()].second.first;
        point v = qaq[i].second.first;
        // cout << u.x << " " << u.y << "!!!\n";
        // cout << v.x << " " << v.y << "???\n";
        st = rotate(u, pi * 1.5), ed = rotate(v, pi / 2.0);
        // st = rotate(u, pi / 2.0), ed = rotate(v, pi * 1.5);
    }
    assert(cnt == 1);
    point S(x0, Y0);
    S = S / S.len() * d;
    
    // cout << st.x << " " << st.y << "??\n";
    // cout << ed.x << " " << ed.y << "??\n";
    // cout << S.x << " " << S.y << "!!\n";
    int l = 0, r = 100000;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(sgn(mid * 2.0 * pi - t) <= 0) l = mid;
        else r = mid - 1;
    }
    // cout << l << "???\n";
    // cout << l << "Q\n";
    // cout << angle(st, ed) << "::\n";
    long double res = angle(st, ed) * l;
    // cout << res << "!!\n";
    t -= l * (2.0 * pi);
    if(S.left(st) > 0 && ed.left(S) > 0) {
        if(sgn(t - angle(S, ed)) <= 0) res += t;
        else {
            t -= angle(S, ed);
            res += angle(S, ed);
            if(sgn(t - angle(ed, st)) > 0) {
                res += t - angle(ed, st);
            }
        }
    } else { 
        // cout << ">>\n";
        if(sgn(t - angle(S, st)) > 0) {
            t -= angle(S, st);
            if(sgn(t - angle(st, ed)) > 0) res += angle(st, ed);
            else res += t;
        }
    }
    cout << res << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T --) sol();
    return 0;
}
/*
3 1 0 1 1
1 2
2 1
2 2

3 1 0 1 2
1 2
2 1
2 2

3 1 0 1 10000
1 2
2 1
2 2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.0000000000

result:

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

Test #2:

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

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.5707963268

result:

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

Test #3:

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

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.7077522575

result:

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

Test #4:

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

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.3841205839

result:

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