Point in Polygon

// clang-format off
#include <bits/stdc++.h>
using namespace std;
#ifdef DO_DBG
namespace std { // these allow printing all pairs, vectors, sets and maps, recursively too
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) 
  { return os << '(' << p.first << ", " << p.second << ')'; }
template <typename T> requires (!std::is_convertible_v<T, const char*>) && ranges::range<T> && (!is_same_v<T, string>)
ostream& operator<<(ostream &os, const T &p) { os << "{ "; for (auto& x : p) os << x << ' '; os << '}'; return os; }
} // end namespace std
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", _dbg_out(__VA_ARGS__)
template <typename T> void _dbg_out(const T &t) { cerr << t << "]\n"; }
template <typename T, typename... Args> void _dbg_out(const T &t, const Args &...args) { cerr << t << ", "; _dbg_out(args...); }
#else
#define dbg(...)
#endif
template <typename... Args> void read(Args&... args) { ((cin >> args), ...); }
template <typename T> using v = vector<T>;
typedef long long ll; typedef long double ld; typedef v<ll> vi; typedef pair<ll, ll> pii; // this template is kactl compatible
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin.exceptions(cin.failbit);
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define rp(n) for (ll i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x)*(x))
#define d(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define dv(x, n) vi x(n); for (size_t i = 0; i < n; i++) cin >> x[i];
#define even(x) ((x)%2==0)
#define odd(x) ((x)%2!=0)
#define sz(s) ((ll)s.size())
#define dist(v,it) distance(v.begin(),it)
typedef complex<ll> Pi;
typedef complex<ld> Pr;
#define X real()
#define Y imag()
#define cross(a,b) (conj(a)*(b)).imag()
// clang-format on

// is point in polygon or it's boundary
int main() {
  ios;
  d(n, m);
  v<Pi> poly(n);
  rp(n) {
    d(x, y);
    poly[i] = Pi(x, y);
  }
  while (m--) {
    d(x, y);
    Pi point = Pi(x, y);
    // we determine if the point is inside the polygon using ray-casting
    // we shoot a ray to the right and count how many edges it intersects
    // if it intersects an odd number of times, the point is inside
    bool inside = false;
    bool boudary = false;
    rep(i, 0, n) {
      Pi a = poly[i] - point;
      Pi b = poly[(i + 1) % n] - point;
      // a and b are the endpoints of the edge relative to point
      // if the cross product is 0, then the point is on the line ab
      // then we just need to check if the point is between a and b
      // by checking that the signs of the x and y coordinates are opposite,
      // which is required if the point goes through the center
      if (cross(a, b) == 0 && (a.X * b.X <= 0) && (a.Y * b.Y <= 0)) {
        boudary = true;
        break;
      }
      // if the ray from the center to the right intersects the edge ab,
      // a and b must be on opposite sides of the x axis
      if (a.Y > b.Y)
        swap(a, b);
      // and we also check that the edge a b is on the right side of the point
      // (center) which is true when the cross product is positive
      if (a.Y <= 0 && b.Y > 0 && cross(a, b) > 0)
        inside = !inside;
    }
    if (boudary)
      cout << "BOUNDARY\n";
    else if (inside)
      cout << "INSIDE\n";
    else
      cout << "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