/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 584.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 2ms 516.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 2ms 540.0 KiB
#6 Accepted 1ms 556.0 KiB
#7 Accepted 1ms 768.0 KiB
#8 Accepted 1ms 332.0 KiB
#9 Accepted 2ms 540.0 KiB
#10 Accepted 2ms 584.0 KiB
#11 Accepted 1ms 584.0 KiB
#12 Accepted 2ms 540.0 KiB
#13 Accepted 2ms 540.0 KiB
#14 Accepted 1ms 540.0 KiB
#15 Accepted 2ms 592.0 KiB
#16 Accepted 2ms 772.0 KiB
#17 Accepted 2ms 540.0 KiB
#18 Accepted 4ms 588.0 KiB
#19 Accepted 2ms 540.0 KiB
#20 Accepted 2ms 588.0 KiB
#21 Accepted 3ms 540.0 KiB
#22 Accepted 3ms 540.0 KiB
#23 Accepted 4ms 588.0 KiB
#24 Accepted 4ms 520.0 KiB
#25 Accepted 3ms 584.0 KiB
#26 Accepted 3ms 588.0 KiB
#27 Accepted 1ms 540.0 KiB
#28 Accepted 1ms 540.0 KiB
#29 Accepted 1ms 540.0 KiB

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using o_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int int64_t
#define double long double
#define endl '\n'
#define X first
#define Y second
#define pii pair<double, double>
#define sz(x) (int) x.size()
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int INF = 1e18 + 10;
const double eps = 1e-4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n; cin>>n;
    vector<pii> v(n);
    for(auto &[a, b] : v) cin>>a>>b;
    pii C{0, 0};
    for(auto &[a, b] : v) C.X += a, C.Y += b;
    C.X /= n, C.Y /= n;
    sort(v.begin(), v.end(), [&] (const auto& A, const auto& B) {
        return atan2(C.Y - A.Y, C.X - A.X) < atan2(C.Y - B.Y, C.X - B.X);
    });

    auto isInside = [&] (pii cur) {

        auto getAng = [&] (pii A, pii B, pii C) {
            double d = atan2(A.Y - C.Y, A.X - C.X) - atan2(B.Y - C.Y, B.X - C.X);
            if(d <= -M_PI) d += 2 * M_PI;
            if(d > M_PI) d -= 2 * M_PI;
            return d;
        };

        double ret = 0;
        for(int i = 0; i < n; i++) ret += getAng(v[i], v[(i + 1) % n], cur);
        if(ret < 0) ret = -ret;
        return abs(ret - 2 * M_PI) < eps;
    };

    pii pt; cin>>pt.X>>pt.Y;

    cout<<(isInside(pt) ? "YES" : "NO")<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1; //cin>>t;
    for(int tc = 1; tc <= t; tc++) {
        // cerr<<"Case "<<tc<<": \n";
        solve();
    }
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Language
C++17 (G++ 13.2.0)
Submit At
2025-06-14 10:01:13
Judged At
2025-06-14 10:01:13
Judged By
Score
100
Total Time
4ms
Peak Memory
772.0 KiB