/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Accepted 1ms 532.0 KiB
#5 Accepted 1ms 532.0 KiB
#6 Accepted 1ms 436.0 KiB
#7 Accepted 1ms 532.0 KiB
#8 Accepted 1ms 532.0 KiB
#9 Accepted 1ms 548.0 KiB
#10 Accepted 1ms 328.0 KiB
#11 Accepted 1ms 484.0 KiB
#12 Accepted 2ms 532.0 KiB
#13 Accepted 1ms 324.0 KiB
#14 Accepted 1ms 532.0 KiB
#15 Accepted 2ms 516.0 KiB
#16 Accepted 2ms 532.0 KiB
#17 Accepted 3ms 324.0 KiB
#18 Accepted 7ms 532.0 KiB
#19 Accepted 5ms 532.0 KiB
#20 Accepted 6ms 532.0 KiB
#21 Accepted 7ms 532.0 KiB
#22 Accepted 7ms 532.0 KiB
#23 Accepted 7ms 576.0 KiB
#24 Accepted 7ms 532.0 KiB
#25 Accepted 7ms 348.0 KiB
#26 Accepted 7ms 532.0 KiB
#27 Accepted 5ms 532.0 KiB
#28 Accepted 2ms 532.0 KiB
#29 Accepted 1ms 532.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 endl '\n'
#define F first
#define S second
#define pii pair<int, int>
#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-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Point {
    double x, y;
};

void solve() {
    int n; cin >> n;
    vector<Point> poly(n);
    for(auto &[x, y] : poly) cin >> x >> y;
    Point pt; cin >> pt.x >> pt.y;

    Point C{0, 0};
    for(auto [x, y] : poly) C.x += x, C.y += y;
    C.x /= n, C.y /= n;
    sort(poly.begin(), poly.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 getAng = [&] (const Point& A, const Point& B, const Point& C) {
        double ret = atan2(C.y - A.y, C.x - A.x) - atan2(C.y - B.y, C.x - B.x);
        if(ret > M_PI) ret -= 2 * M_PI;
        if(ret < -M_PI) ret += 2 * M_PI;
        return ret;
    };

    auto isInside = [&] (Point& A, vector<Point>& poly) {
        int n = sz(poly);
        double sm = 0;

        for(int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            sm += getAng(poly[i], poly[j], A);
        }
        if(sm < 0) sm = -sm;
        return abs(sm - 2 * M_PI) < eps;
    };

    cout << (isInside(pt, poly) ? "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-07-07 10:35:53
Judged At
2025-07-07 10:35:53
Judged By
Score
100
Total Time
7ms
Peak Memory
576.0 KiB