Point in Polygon.


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

Se le proporciona un polígono de n vértices y una lista de m puntos. Su tarea consiste en determinar, para cada punto, si está dentro, fuera o en el límite del polígono. El polígono consta de n vértices (x_1,y_1),(x_2,y_2),\dots,(x_n,y_n). Los vértices (x_i,y_i) y (x_{i+1},y_{i+1}) son adyacentes para i=1,2,\dots,n-1, y los vértices (x_1,y_1) y (x_n,y_n) también lo son.

Entrada

La primera línea de entrada tiene dos enteros n y m: el número de vértices del polígono y el número de puntos.

Después de esto, hay n líneas que describen el polígono. La i-ésima línea tiene dos enteros x_i e y_i. Se puede asumir que el polígono es simple, es decir, no se intersecta consigo mismo.

Finalmente, hay m líneas que describen los puntos. Cada línea tiene dos enteros x e y.

Salida

Para cada punto, escriba "INSIDE", "OUTSIDE" o "BOUNDARY".

Restricciones

  • 3 \leq n,m \leq 1000
  • 1 \leq m \leq 1000
  • -10^9 \leq x_i, y_i \leq 10^9
  • -10^9 \leq x, y \leq 10^9

Ejemplo de Entrada

4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3

Ejemplo de Salida

INSIDE
OUTSIDE
BOUNDARY

Comments

There are no comments at the moment.