QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#551196#9253. Prism Palaceucup-team112#AC ✓91ms40828kbC++2012.2kb2024-09-07 15:55:122024-09-07 15:55:13

Judging History

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

  • [2024-09-07 15:55:13]
  • 评测
  • 测评结果:AC
  • 用时:91ms
  • 内存:40828kb
  • [2024-09-07 15:55:12]
  • 提交

answer

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #define INTERACTIVE

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

namespace templates {
// type
using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pil = pair<int, ll>;
using Pli = pair<ll, int>;
using Pll = pair<ll, ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using qp = priority_queue<T, vector<T>, greater<T>>;
// clang-format off
#define vec(T, A, ...) vector<T> A(__VA_ARGS__);
#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));
#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));
// clang-format on

// for loop
#define fori1(a) for (ll _ = 0; _ < (a); _++)
#define fori2(i, a) for (ll i = 0; i < (a); i++)
#define fori3(i, a, b) for (ll i = (a); i < (b); i++)
#define fori4(i, a, b, c) for (ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))
#define overload4(a, b, c, d, e, ...) e
#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)

// declare and input
// clang-format off
#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);
#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);
#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);
#define DOUBLE(...) double __VA_ARGS__; STRING(str___); __VA_ARGS__ = stod(str___);
#define VEC(T, A, n) vector<T> A(n); inp(A);
#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);
// clang-format on

// const value
const ll MOD1   = 1000000007;
const ll MOD9   = 998244353;
const double PI = acos(-1);

// other macro
#if !defined(RIN__LOCAL) && !defined(INTERACTIVE)
#define endl "\n"
#endif
#define spa ' '
#define len(A) ll(A.size())
#define all(A) begin(A), end(A)

// function
vector<char> stoc(string &S) {
    int n = S.size();
    vector<char> ret(n);
    for (int i = 0; i < n; i++) ret[i] = S[i];
    return ret;
}
string ctos(vector<char> &S) {
    int n      = S.size();
    string ret = "";
    for (int i = 0; i < n; i++) ret += S[i];
    return ret;
}

template <class T>
auto min(const T &a) {
    return *min_element(all(a));
}
template <class T>
auto max(const T &a) {
    return *max_element(all(a));
}
template <class T, class S>
auto clamp(T &a, const S &l, const S &r) {
    return (a > r ? r : a < l ? l : a);
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chclamp(T &a, const S &l, const S &r) {
    auto b = clamp(a, l, r);
    return (a != b ? a = b, 1 : 0);
}

template <typename T>
T sum(vector<T> &A) {
    T tot = 0;
    for (auto a : A) tot += a;
    return tot;
}

template <typename T>
vector<T> compression(vector<T> X) {
    sort(all(X));
    X.erase(unique(all(X)), X.end());
    return X;
}

// input and output
namespace io {
// __int128_t
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[128];
        char *d = std::end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = std::end(buffer) - d;
        if (dest.rdbuf()->sputn(d, len) != len) {
            dest.setstate(std::ios_base::badbit);
        }
    }
    return dest;
}

// vector<T>
template <typename T>
istream &operator>>(istream &is, vector<T> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << ' ';
    }
    return os;
}

// vector<vector<T>>
template <typename T>
istream &operator>>(istream &is, vector<vector<T>> &A) {
    for (auto &a : A) is >> a;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// pair<S, T>
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &A) {
    is >> A.first >> A.second;
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, pair<S, T> &A) {
    os << A.first << ' ' << A.second;
    return os;
}

// vector<pair<S, T>>
template <typename S, typename T>
istream &operator>>(istream &is, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        is >> A[i];
    }
    return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, vector<pair<S, T>> &A) {
    for (size_t i = 0; i < A.size(); i++) {
        os << A[i];
        if (i != A.size() - 1) os << endl;
    }
    return os;
}

// tuple
template <typename T, size_t N>
struct TuplePrint {
    static ostream &print(ostream &os, const T &t) {
        TuplePrint<T, N - 1>::print(os, t);
        os << ' ' << get<N - 1>(t);
        return os;
    }
};
template <typename T>
struct TuplePrint<T, 1> {
    static ostream &print(ostream &os, const T &t) {
        os << get<0>(t);
        return os;
    }
};
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t) {
    TuplePrint<decltype(t), sizeof...(Args)>::print(os, t);
    return os;
}

// io functions
void FLUSH() {
    cout << flush;
}

void print() {
    cout << endl;
}
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
    cout << head;
    if (sizeof...(Tail)) cout << spa;
    print(std::forward<Tail>(tail)...);
}

template <typename T, typename S>
void prisep(vector<T> &A, S sep) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << sep;
    }
    cout << endl;
}
template <typename T, typename S>
void priend(T A, S end) {
    cout << A << end;
}
template <typename T>
void prispa(T A) {
    priend(A, spa);
}
template <typename T, typename S>
bool printif(bool f, T A, S B) {
    if (f)
        print(A);
    else
        print(B);
    return f;
}

template <class... T>
void inp(T &...a) {
    (cin >> ... >> a);
}

} // namespace io
using namespace io;

// read graph
vector<vector<int>> read_edges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<int>> edges(n, vector<int>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        u -= indexed;
        v -= indexed;
        edges[u].push_back(v);
        if (!direct) edges[v].push_back(u);
    }
    return edges;
}
vector<vector<int>> read_tree(int n, int indexed = 1) {
    return read_edges(n, n - 1, false, indexed);
}

template <typename T = long long>
vector<vector<pair<int, T>>> read_wedges(int n, int m, bool direct = false, int indexed = 1) {
    vector<vector<pair<int, T>>> edges(n, vector<pair<int, T>>());
    for (int i = 0; i < m; i++) {
        INT(u, v);
        T w;
        inp(w);
        u -= indexed;
        v -= indexed;
        edges[u].push_back({v, w});
        if (!direct) edges[v].push_back({u, w});
    }
    return edges;
}
template <typename T = long long>
vector<vector<pair<int, T>>> read_wtree(int n, int indexed = 1) {
    return read_wedges<T>(n, n - 1, false, indexed);
}

// yes / no
namespace yesno {

// yes
inline bool yes(bool f = true) {
    cout << (f ? "yes" : "no") << endl;
    return f;
}
inline bool Yes(bool f = true) {
    cout << (f ? "Yes" : "No") << endl;
    return f;
}
inline bool YES(bool f = true) {
    cout << (f ? "YES" : "NO") << endl;
    return f;
}

// no
inline bool no(bool f = true) {
    cout << (!f ? "yes" : "no") << endl;
    return f;
}
inline bool No(bool f = true) {
    cout << (!f ? "Yes" : "No") << endl;
    return f;
}
inline bool NO(bool f = true) {
    cout << (!f ? "YES" : "NO") << endl;
    return f;
}

// possible
inline bool possible(bool f = true) {
    cout << (f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Possible(bool f = true) {
    cout << (f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool POSSIBLE(bool f = true) {
    cout << (f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// impossible
inline bool impossible(bool f = true) {
    cout << (!f ? "possible" : "impossible") << endl;
    return f;
}
inline bool Impossible(bool f = true) {
    cout << (!f ? "Possible" : "Impossible") << endl;
    return f;
}
inline bool IMPOSSIBLE(bool f = true) {
    cout << (!f ? "POSSIBLE" : "IMPOSSIBLE") << endl;
    return f;
}

// Alice Bob
inline bool Alice(bool f = true) {
    cout << (f ? "Alice" : "Bob") << endl;
    return f;
}
inline bool Bob(bool f = true) {
    cout << (f ? "Bob" : "Alice") << endl;
    return f;
}

// Takahashi Aoki
inline bool Takahashi(bool f = true) {
    cout << (f ? "Takahashi" : "Aoki") << endl;
    return f;
}
inline bool Aoki(bool f = true) {
    cout << (f ? "Aoki" : "Takahashi") << endl;
    return f;
}

} // namespace yesno
using namespace yesno;

} // namespace templates
using namespace templates;

void solve() {
    INT(n);
    VEC(Pll, P, n);
    using ld  = long double;
    using Pdi = pair<ld, int>;
    vec(Pdi, imos, 0);
    imos.push_back({-PI, 0});
    imos.push_back({PI, 0});

    fori(i, n) {
        int bi = i == 0 ? n - 1 : i - 1;
        i - 1;
        ll dx = P[i].first - P[bi].first;
        ll dy = P[i].second - P[bi].second;
        ld d  = atan2(dy, dx);
        if (d < 0) {
            imos.push_back({d, 1});
            imos.push_back({d + PI, -1});
        } else {
            imos.push_back({-PI, 1});
            imos.push_back({d - PI, -1});
            imos.push_back({d, 1});
            imos.push_back({PI, -1});
        }
    }

    sort(all(imos));
    double ans = 0;
    ll tot     = 0;
    ld b       = -PI;

    for (auto [d, c] : imos) {
        if (tot == 1 or tot == n - 1) {
            ans += d - b;
        }
        tot += c;
        b = d;
    }

    ans /= 2 * PI;
    print(ans);
}

int main() {
#ifndef INTERACTIVE
    std::cin.tie(0)->sync_with_stdio(0);
#endif
    std::cout << std::fixed << std::setprecision(12);
    int t;
    t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

// // #pragma GCC target("avx2")
// // #pragma GCC optimize("O3")
// // #pragma GCC optimize("unroll-loops")
// // #define INTERACTIVE
//
// #include "kyopro-cpp/template.hpp"
//
// void solve() {
//     INT(n);
//     VEC(Pll, P, n);
//     using ld  = long double;
//     using Pdi = pair<ld, int>;
//     vec(Pdi, imos, 0);
//     imos.push_back({-PI, 0});
//     imos.push_back({PI, 0});
//
//     fori(i, n) {
//         int bi = i == 0 ? n - 1 : i - 1;
//         i - 1;
//         ll dx = P[i].first - P[bi].first;
//         ll dy = P[i].second - P[bi].second;
//         ld d  = atan2(dy, dx);
//         if (d < 0) {
//             imos.push_back({d, 1});
//             imos.push_back({d + PI, -1});
//         } else {
//             imos.push_back({-PI, 1});
//             imos.push_back({d - PI, -1});
//             imos.push_back({d, 1});
//             imos.push_back({PI, -1});
//         }
//     }
//
//     sort(all(imos));
//     double ans = 0;
//     ll tot     = 0;
//     ld b       = -PI;
//
//     for (auto [d, c] : imos) {
//         if (tot == 1 or tot == n - 1) {
//             ans += d - b;
//         }
//         tot += c;
//         b = d;
//     }
//
//     ans /= 2 * PI;
//     print(ans);
// }
//
// int main() {
// #ifndef INTERACTIVE
//     std::cin.tie(0)->sync_with_stdio(0);
// #endif
//     std::cout << std::fixed << std::setprecision(12);
//     int t;
//     t = 1;
//     // std::cin >> t;
//     while (t--) solve();
//     return 0;
// }

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

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

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: 0
Accepted
time: 0ms
memory: 4116kb

input:

4
0 0
0 1
1 1
1 0

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #3:

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

input:

4
0 0
0 3
1 2
1 1

output:

0.500000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 91ms
memory: 40676kb

input:

199996
719157942 80035870
719158808 80033199
719160795 80027070
719162868 80020675
719165635 80012139
719166422 80009711
719166927 80008153
719168388 80003645
719168539 80003179
719168806 80002355
719168864 80002176
719169119 80001389
719171067 79995376
719173806 79986921
719175195 79982633
71917686...

output:

0.000077716803

result:

ok found '0.0000777', expected '0.0000777', error '0.0000000'

Test #5:

score: 0
Accepted
time: 83ms
memory: 40828kb

input:

199999
521578765 315995242
521578784 315995230
521585008 315991299
521590377 315987908
521597318 315983524
521606119 315977965
521610976 315974897
521614329 315972779
521622922 315967351
521631939 315961655
521636172 315958981
521638241 315957674
521643115 315954595
521650976 315949629
521656567 315...

output:

0.000096532179

result:

ok found '0.0000965', expected '0.0000965', error '0.0000000'

Test #6:

score: 0
Accepted
time: 76ms
memory: 39652kb

input:

200000
88808852 208512084
88810113 208513562
88812008 208515783
88812543 208516410
88816806 208521406
88824507 208530431
88825624 208531740
88831723 208538887
88834262 208541862
88838287 208546578
88845440 208554959
88848801 208558897
88855564 208566821
88856869 208568350
88862876 208575388
88868324...

output:

0.000074373701

result:

ok found '0.0000744', expected '0.0000744', error '0.0000000'

Test #7:

score: 0
Accepted
time: 85ms
memory: 40560kb

input:

199998
2857588 37580055
2857908 37582176
2857951 37582461
2858026 37582958
2859295 37591366
2859678 37593903
2860879 37601857
2862301 37611272
2862330 37611464
2863054 37616255
2864429 37625353
2865434 37632002
2865585 37633001
2867092 37642971
2867321 37644486
2867870 37648118
2868343 37651247
2868...

output:

0.000067539683

result:

ok found '0.0000675', expected '0.0000675', error '0.0000000'

Test #8:

score: 0
Accepted
time: 70ms
memory: 40548kb

input:

199999
487716180 333296644
487720319 333294576
487721706 333293883
487731571 333288954
487734599 333287441
487742738 333283374
487744419 333282534
487746174 333281657
487748301 333280594
487750462 333279514
487754846 333277323
487759670 333274912
487762097 333273699
487764676 333272410
487772963 333...

output:

0.000070696702

result:

ok found '0.0000707', expected '0.0000707', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed