Point in Polygon

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
#include <complex>

using namespace std;

typedef long long ll;
typedef complex<ll> P;

ll cross(P a, P b) {
    return (conj(a) * b).imag();
}

ll dot(P a, P b) {
    return (conj(a) * b).real();
}

int sgn(ll x) { return (x > 0) - (x < 0); }

bool onSeg(P a, P b, P c) {
    if (sgn(cross(b - a, c - a)) != 0) return false;
    return sgn(dot(c - a, c - b)) <= 0;
}

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

    // freopen("input.txt", "r", stdin);

    int n, m;
    cin >> n >> m;
    vector<P> points(n);
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        points[i] = P(x, y);
    }
    points.push_back(points[0]);

    for (int i = 0; i < m; i++) {
        ll x, y;
        cin >> x >> y;
        P point = P(x, y);
        int state = 1; // 0 - boundary, 1 - inside, -1 - outside

        bool inside = false;
        for (int j = 0; j < n; j++) {
            P a = points[j];
            P b = points[j + 1];

            if (onSeg(a, b, point)) {
                state = 0;
                break;
            }

            ll ay = a.imag(), by = b.imag();
            if ((ay > y) != (by > y)) {
                ll dy = by - ay;
                ll lhs = (x - a.real()) * dy;
                ll rhs = (b.real() - a.real()) * (y - ay);
                if ((dy > 0 && lhs < rhs) || (dy < 0 && lhs > rhs)) {
                    inside = !inside;
                }
            }
        }

        if (state == 0) {
            cout << "BOUNDARY\n";
        } else {
            cout << (inside ? "INSIDE\n" : "OUTSIDE\n");
        }
    }
}

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