Point in Polygon

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define VI vector<int>
#define AR(x) array<int, x>
#define MX vector<VI >
#define all(x) x.begin(), x.end()
#define IOS cin.tie(0)->sync_with_stdio(0)

using namespace std;

mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());

double rnd(){
    return uniform_real_distribution<double>(0, 1)(rng32);
}
int rnd(int a, int b){
    return uniform_int_distribution<int>(a, b)(rng32);
}

using C = complex<ll>;

int main(){

    int n, m;
    cin >> n >> m;

    vector<C > p(n);
    
    ll ma = 0;
    for(auto &c : p){
        ll x, y;
        cin >> x >> y;
        c = {x, y};
        ma = max(ma, x);
    }

    auto cross = [](C a, C b){ return (conj(a)*b).imag(); };

    for(int i=0; i<m; i++){
        C a, b; ll xx, yy;
        cin >> xx >> yy;
        a = {xx, yy};
        b = {ma+123, yy+1};
        int cnt = 0;
        bool boundary = 0;
        for(int j=0; j<n; j++){
            auto p1 = p[j];
            auto p2 = p[(j+1)%n];
            ll s1 = cross(a-p1, a-p2);
            ll s2 = cross(b-p1, b-p2);
            ll s3 = cross(p1-a, p1-b);
            ll s4 = cross(p2-a, p2-b);
            if(s1 == 0){
                C a1 = a-p1, a2 = a-p2;
                if(a1.real()*a2.real()+a1.imag()*a2.imag() <= 0) boundary = true;
            }
            if((s1 > 0) != (s2 > 0) && (s3 > 0) != (s4 > 0)) cnt++;
        }
        if(boundary) cout << "BOUNDARY\n";
        else if(cnt&1) cout << "INSIDE\n";
        else cout << "OUTSIDE\n";
    }

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED