QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#551684#9253. Prism Palaceucup-team3584#WA 1ms4060kbC++203.6kb2024-09-07 17:46:192024-09-07 17:46:20

Judging History

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

  • [2024-09-07 17:46:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4060kb
  • [2024-09-07 17:46:19]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }
    x.push_back(x[0]), y.push_back(y[0]);
    vector<pair<ll, ll>> v(n);
    for (int i = 0; i < n; ++i) {
        v[i].first = x[i + 1] - x[i];
        v[i].second = y[i + 1] - y[i];
    }
    map<pair<ll, ll>, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        if (v[i].first == 0) {
            mp[{1, 0}].push_back(i);
        } else if (v[i].second == 0) {
            mp[{0, 1}].push_back(i);
        } else {
            if (v[i].first < 0) {
                v[i].first = -v[i].first, v[i].second = -v[i].second;
            }
            ll a = v[i].first, b = v[i].second;
            ll g = gcd(a, abs(b));
            a /= g, b /= g;
            mp[{a, -b}].push_back(i);
        }
    }

    double res = 0;
    vector<pair<ll, ll>> ang;
    ang.emplace_back(0, 1);
    ang.emplace_back(1, 0);
    for (const auto &p : mp) {
        ang.push_back(p.first);
    }
    sort(ang.begin(), ang.end());
    ang.erase(unique(ang.begin(), ang.end()), ang.end());
    sort(ang.begin(), ang.end(), [&](auto p, auto q) {
        if (p.first == 0) return true;
        if (q.first == 0) return false;
        return p.second * q.first > p.first * q.second;
    });

    vector<bool> minus(n);
    multiset<pair<ll, ll>> st;
    ll xs = 0, ys = 0;
    for (int i = 0; i < n; ++i) {
        if (v[i].second >= 0) {
            minus[i] = false;
            st.insert({v[i].first, v[i].second});
            xs += v[i].first, ys += v[i].second;
        } else {
            minus[i] = true;
            st.insert({-v[i].first, -v[i].second});
            xs -= v[i].first, ys -= v[i].second;
        }
    }

    auto calc = [&](ll px, ll py, ll nx, ll ny) -> void {
        ll uo = px * px + py * py + nx * nx + ny * ny - (px - nx) * (px - nx) - (py - ny) * (py - ny);
        ll ui = 4LL * (px * px + py * py) * (nx * nx + ny * ny);
        long double cs = uo / sqrt((long double)ui);
        long double p = acos(cs) / acos((long double)-1.0) / 2;
        res += p;
    };
    auto update = [&](int j) {
        ll a = v[j].first, b = v[j].second;
        if (minus[j]) a = -a, b = -b, minus[j] = false;
        else minus[j] = true;
        auto it = st.find({a, b});
        st.erase({a, b});
        st.insert({-a, -b});
        xs -= 2LL * a, ys -= 2LL * b;
    };

    ll px = 0, py = 1;
    for (int i = 1; i < ang.size(); ++i) {
        ll nx = ang[i].first, ny = ang[i].second;
        if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
            calc(px, py, nx, ny);
        }
        for (auto j : mp[ang[i]]) {
            update(j);
        }
        px = nx, py = ny;
    }
    for (int i = 0; i < ang.size(); ++i) {
        ll nx = -ang[i].first, ny = -ang[i].second;
        if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
            calc(px, py, nx, ny);
        }
        for (auto j : mp[ang[i]]) {
            update(j);
        }
        px = nx, py = ny;
    }
    {
        ll nx = ang[0].first, ny = ang[0].second;
        if (xs % 2 == 0 and ys % 2 == 0 and st.find({xs / 2, ys / 2}) != st.end()) {
            calc(px, py, nx, ny);
        }
    }

    printf("%.12f\n", res);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4060kb

input:

3
0 0
1 0
0 1

output:

1.000000000000

result:

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

Test #2:

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

input:

4
0 0
0 1
1 1
1 0

output:

1.000000000000

result:

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