/ 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 2ms 348.0 KiB
#5 Accepted 1ms 768.0 KiB
#6 Accepted 1ms 540.0 KiB
#7 Accepted 1ms 556.0 KiB
#8 Accepted 2ms 512.0 KiB
#9 Accepted 1ms 584.0 KiB
#10 Accepted 2ms 328.0 KiB
#11 Accepted 2ms 492.0 KiB
#12 Accepted 2ms 332.0 KiB
#13 Accepted 2ms 436.0 KiB
#14 Accepted 1ms 512.0 KiB
#15 Accepted 1ms 332.0 KiB
#16 Accepted 1ms 332.0 KiB
#17 Accepted 1ms 540.0 KiB
#18 Accepted 3ms 588.0 KiB
#19 Accepted 2ms 352.0 KiB
#20 Accepted 2ms 580.0 KiB
#21 Accepted 3ms 492.0 KiB
#22 Accepted 3ms 512.0 KiB
#23 Accepted 3ms 540.0 KiB
#24 Accepted 2ms 768.0 KiB
#25 Accepted 2ms 588.0 KiB
#26 Accepted 3ms 540.0 KiB
#27 Accepted 1ms 328.0 KiB
#28 Accepted 2ms 500.0 KiB
#29 Accepted 1ms 332.0 KiB

Code

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

const double eps = 1e-9;
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); }
    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; }

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

int winding_number(vector<PT> &p, const PT& z) {
    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 = (p[j].y - p[i].y) * (z.x - p[i].x) > (z.y - p[i].y) * (p[j].x - p[i].x);
            if (below == orient) ans += below ? 1 : -1;
        }
    }
    return ans;
}

// From template: -1 if strictly inside, 0 if on the polygon, 1 if strictly outside
int is_point_in_polygon(vector<PT> &p, const PT& z) {
    int k = winding_number(p, z);
    return k == 1e9 ? 0 : k == 0 ? 1 : -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<PT> path(n);
    for(int i = 0; i < n; i++) {
        cin >> path[i].x >> path[i].y;
    }
    
    PT novita;
    cin >> novita.x >> novita.y;
    
    // -1 means strictly inside -> YES
    // 0 means on polygon -> NO
    // 1 means strictly outside -> NO
    cout << (is_point_in_polygon(path, novita) == -1 ? "YES\n" : "NO\n");
    
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Contest
LU Divisonal Contest Problem Testing Round
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-05 06:35:48
Judged At
2024-12-05 06:35:48
Judged By
Score
100
Total Time
3ms
Peak Memory
768.0 KiB