Algorytmy 2
Punkt i wielokąt
Dany jest wielokąt o $n$ wierzchołkach i lista $m$ punktów. Twoim zadaniem jest określenie dla każdego punktu z listy, czy znajduje się on wewnątrz, zewnątrz czy też na brzegu wielokąta. Wielokąt zadany jest przez $n$ wierzchołków $(x_1,y_1)$, $(x_2,y_2)$, $\dots$, $(x_n,y_n)$. Wierzchołki $(x_i,y_i)$ i $(x_{i+1},y_{i+1})$ sąsiadują ze sobą dla $i=1,2,\dots,n-1$, wierzchołki $(x_1,y_1)$ i $(x_n ,y_n)$ również sąsiadują ze sobą.
Wejście
Pierwsza linia wejściowa zawiera dwie liczby całkowite $n$ i $m$: liczbę wierzchołków wielokąta i liczbę punktów. Następne $n$ linii opisuje wielokąt. $i$-ta taka linia zawiera dwie liczby całkowite $x_i$ i $y_i$. Można założyć, że wielokąt jest prosty. Kolejne $m$ linii zawiera listę punktów do przetestowania. W każdym wierszu znajdują się dwie liczby całkowite x i y.
Wyjście
Dla każdego punktu wypisz "INSIDE", "OUTSIDE" lub "BOUNDARY".
Ograniczenia
- $3 \le n,m \le 1000$
- $1 \le m \le 1000$
- $-10^9 \le x_i, y_i \le 10^9$
- $-10^9 \le x, y \le 10^9$
Przykłady
Wejście 1
4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3
Wyjście 1
INSIDE
OUTSIDE
BOUNDARY