【題解】CSES 2192 Point in Polygon

【題目敘述】https://cses.fi/problemset/task/2192/

#include <iostream>
using namespace std;
 
int n, m;
 
struct Point{
    long long x, y;
    Point operator+(Point b){
        return {x+b.x, y+b.y};
    }
    Point operator-(Point b){
        return {x-b.x, y-b.y};
    }
}p, a[1005];
 
long long cross(Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
 
long long dot(Point a, Point b){
    return a.x*b.x + a.y*b.y;
}
 
int sign(long long x){
    if (x > 0) return 1;
    else if (x < 0) return -1;
    else return 0;
}
 
bool onseg(Point a, Point b, Point c){
    if (cross(c-a, b-a) != 0) return false;
    if (0 <= dot(c-a, b-a) && dot(c-a, b-a) <= dot(b-a, b-a)) return true;
    return false;
}
 
bool intersec(Point a, Point b, Point c, Point d){
    int f1 = sign(cross(a-c, d-c)) * sign(cross(b-c, d-c));
    int f2 = sign(cross(c-a, b-a)) * sign(cross(d-a, b-a));
    if (f1 < 0 && f2 < 0) return true;
    if (f1 > 0 || f2 > 0) return false;
    if (onseg(a, b, c)) return true;
    if (onseg(a, b, d)) return true;
    if (onseg(c, d, a)) return true;
    if (onseg(c, d, b)) return true;
    return false;
}
 
void point_in_polygon(Point x, Point a[]){
    for (int i = 1; i < n; i++){
        if (onseg(a[i-1], a[i], x)){
            cout << "BOUNDARY\n";
            return;
        }
    }
    if (onseg(a[n-1], a[0], x)){
        cout << "BOUNDARY\n";
        return;
    }
    Point y = x + Point{1, (long long)2e9+5};
    int cnt = 0;
    for (int i = 1; i < n; i++){
        if (intersec(x, y, a[i-1], a[i])) cnt++;
    }
    if (intersec(x, y, a[n-1], a[0])) cnt++;
    if (cnt % 2 == 1) cout << "INSIDE\n";
    else cout << "OUTSIDE\n";
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 0; i < m; i++){
        cin >> p.x >> p.y;
        point_in_polygon(p, a);
    }
}
分享本文 Share with friends