/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 1ms 540.0 KiB
#3 Accepted 1ms 540.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 328.0 KiB
#8 Accepted 1ms 772.0 KiB
#9 Accepted 2ms 512.0 KiB
#10 Accepted 1ms 540.0 KiB
#11 Accepted 1ms 584.0 KiB
#12 Accepted 2ms 540.0 KiB
#13 Accepted 1ms 768.0 KiB
#14 Accepted 1ms 796.0 KiB
#15 Accepted 1ms 332.0 KiB
#16 Accepted 1ms 540.0 KiB
#17 Accepted 2ms 328.0 KiB
#18 Accepted 2ms 772.0 KiB
#19 Accepted 2ms 328.0 KiB
#20 Accepted 1ms 540.0 KiB
#21 Accepted 2ms 772.0 KiB
#22 Accepted 2ms 560.0 KiB
#23 Accepted 2ms 540.0 KiB
#24 Accepted 2ms 540.0 KiB
#25 Accepted 2ms 816.0 KiB
#26 Accepted 2ms 772.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>
using namespace std;

typedef long long ll;
#define bug(a) cout << #a << " : " << a << endl;

const double inf = 1e100;
const double eps = 1e-9;
const double PI = acos((double)-1.0);
int sign(double x) { return (x > eps) - (x < -eps); }
struct PT {
    double x, y;
    PT() { x = 0, y = 0; }
    PT(double x, double y) : x(x), y(y) {}
    PT operator - (const PT &a) const { return PT(x - a.x, y - a.y); }
};
inline double cross(PT a, PT b) { return a.x * b.y - a.y * b.x; }
inline double cross2(PT a, PT b, PT c) { return cross(b - a, c - a); }

bool is_point_on_seg(PT a, PT b, PT p) {
    if (fabs(cross(p - b, a - b)) < eps) {
        if (p.x < min(a.x, b.x) - eps || p.x > max(a.x, b.x) + eps) return false;
        if (p.y < min(a.y, b.y) - eps || p.y > max(a.y, b.y) + eps) return false;
        return true;
    }
    return false;
}
bool is_point_on_polygon(vector<PT> &p, const PT& z) {
    int n = p.size();
    for (int i = 0; i < n; i++) {
    	if (is_point_on_seg(p[i], p[(i + 1) % n], z)) return 1;
    }
    return 0;
}
inline int orientation(PT a, PT b, PT c) { return sign(cross(b - a, c - a)); }

// returns 1e9 if the point is on the polygon 
int winding_number(vector<PT> &p, const PT& z) { // O(n)
    if (is_point_on_polygon(p, z)) return 1e9;
    int n = p.size(), ans = 0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        bool below = p[i].y < z.y;
        if (below != (p[j].y < z.y)) {
            auto orient = orientation(z, p[j], p[i]);
            if (orient == 0) return 0;
            if (below == (orient > 0)) ans += below ? 1 : -1;
        }
    }
    return ans;
}
// -1 if strictly inside, 0 if on the polygon, 1 if strictly outside
int is_point_in_polygon(vector<PT> &p, const PT& z) { // O(n)
    int k = winding_number(p, z);
    return k == 1e9 ? 0 : k == 0 ? 1 : -1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    while (t--) {
        int n; cin >> n;
        vector<PT> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i].x>>v[i].y;
        }
        PT a;cin>>a.x>>a.y;
        if(is_point_in_polygon(v,a)==-1)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-14 18:45:32
Judged At
2024-12-14 18:45:32
Judged By
Score
100
Total Time
2ms
Peak Memory
816.0 KiB