# 【題解】CSES 2192 Point in Polygon

```#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);
}
}
```