/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Accepted 1ms 532.0 KiB
#3 Accepted 1ms 532.0 KiB
#4 Wrong Answer 1ms 540.0 KiB
#5 Accepted 1ms 508.0 KiB
#6 Accepted 1ms 536.0 KiB
#7 Accepted 1ms 324.0 KiB
#8 Wrong Answer 1ms 336.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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Point {
    int 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;

    auto getArea = [&] (vector<Point>& poly) {
        int n = sz(poly), ret = 0;

        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);
        });

        for(int i = 0; i < n; i++) ret += poly[i].x * poly[(i + 1) % n].y - poly[(i + 1) % n].x * poly[i].y;

        return abs(ret);
    };

    auto ori = [&] (const Point& A, const Point& B, const Point& C) {
        int cur = (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
        return cur == 0 ? 0 : cur > 0 ? +1 : -1;
    };

    auto onSeg = [&] (const Point& A, const Point& B, const Point& C) {
        if(ori(A, B, C)) return false;
        return (min(A.x, B.x) <= C.x && C.x <= max(A.x, B.x)) && (min(A.y, B.y) <= C.y && C.y <= max(A.y, B.y));
    };

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

        // for(auto [x, y] : poly) cerr << x << " " << y << endl;

        for(int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            if(onSeg(poly[i], poly[j], A)) return false;
            vector<Point> t = {poly[i], poly[j], A};
            sm += getArea(t);
        }

        return cur == sm;
    };

    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:24:53
Judged At
2025-07-07 10:24:53
Judged By
Score
20
Total Time
1ms
Peak Memory
540.0 KiB