Problema C - El huerto

Entrada: huerto.in
Salida: estándar
Máxima memoria: 32 MB
Tiempo límite: 10 segundos

Descripción

Doña Leonor acaba de tirar la antigua reja que delimitaba su huerto de manzanos porque ordenó una nueva reja electrificada para proteger mejor su propiedad. El huerto tiene la forma de un polígono convexo (es decir, un polígono cuyas diagonales quedan todas en su interior). Fuera del huerto siempre han crecido de manera natural algunos manzanos y los pobladores del pueblo vecino suelen tomar fruta libremente de ellos. Pero ahora, mientras Doña Leonor está en espera de que le envíen la nueva reja los campesinos ya no saben cuáles árboles pertenecen al huerto y cuáles no. Lo único que queda de la reja antigua son los postes grandes colocados en las esquinas del huerto, o sea en los vértices del polígono. Escribe un programa que les permita a los pobladores determinar si un manzano dado pertenece o no al huerto de Doña Leonor (puedes suponer que no hay árboles en la orilla del terreno).

Entrada

La entrada consiste de varios casos de prueba. En la primera línea de cada caso se encuentran los enteros positivos n y m que representan, respectivamente, el número de lados del huerto de Doña Leonor y el número de árboles que hay que ubicar (3 ≤ n ≤ 20 y 1 ≤ m ≤ 100). La segunda línea de cada caso contiene 2n enteros x1 y1 x2 y2 … xn yn que representan las coordenadas de los n vértices del huerto en orden consecutivo de cómo estaba conectada la malla, todos con un valor absoluto menor o igual que 300. La tercera línea de cada caso contiene 2m enteros mx1 my1 mx2 my2 … mxm mym, que representan las coordenadas de los manzanos. La entrada concluye cuando n = m = 0, este caso no debe ser procesado.

Salida

Para cada caso de prueba, imprime m+1 líneas. La primera debe contener el número del caso y las siguientes m deben contener la ubicación de los árboles de acuerdo al formato de salida mostrado en el ejemplo. Coloca una línea en blanco entre salidas de casos diferentes. Los manzanos están numerados según el orden en el que aparecieron en la entrada.

Ejemplo de entrada	Ejemplo de salida
4 2 0 2 2 1 1 -1 -1 0 1 1 0 -1 3 3 0 3 -2 1 3 -2 0 0 1 2 2 0 0 0	Huerto #1 Manzano #1: dentro Manzano #2: fuera Huerto #2 Manzano #1: dentro Manzano #2: fuera Manzano #3: fuera

Regresar