Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Freyja es la diosa del amor, sexo, belleza, fertilidad y otras cosas. A diferencia de Odín, quien es un dios Aesir, Freyja es miembro de los Vanir. Esas son las dos facciones opuestas de los dioses que han peleado en el pasado en el cual los Aesir ganaron. Freyja y su hermano Freyr son dos rehenes tomados por los Aesir, ellos vivieron en Asgard por un tiempo. Como un acuerdo entre las dos facciones, Freyja puede tomar la mitad de los muertos que murieron valientemente en la batalla a su reino de Folkvang en el más allá, mientras que la otra mitad va al salón Odín de Valhalla. Freyja es una apasionada buscadora de placer y emoción. Sin embargo, ella también es una poderosa practicante de la forma chamánica de magia, Seidr. La magia Seidr funciona discerniendo el tejido del destino y rehaciendo parte de este para manipular los deseos, la salud y la prosperidad de los demás.

Aunque los humanos no somos tan conocedores como Freyja, practicar Seidr nosotros mismos no es del todo imposible. Sabemos solo algunas cosas sobre los patrones del destino y solo podemos acceder a un número bastante pequeño de este (de lo contrario obtendremos TLE), pero hay algo que podemos hacer. El tejido del destino luce básicamente como una gran cantidad de puntos en el plano y se pueden conectar para formar segmentos. Debido a que somos meros humanos, podemos operar solo en un plano bidimensional. De esta manera, una de la forma más básica de conectar estos puntos es formando triángulos. ¡Tenga en cuenta que dos segmentos no pueden cruzarse! Más formalmente, se le dará primero un polígono convexo como el límite del alcance de su manipulación. (Este es un paso muy importante en la práctica de la magia, para establecer el límite. A menudo los desastres suceden cuando uno descuida este paso básico.) Y luego se le dará un conjunto de puntos. Con estos puntos, tendrá que cortar el polígono en varios triángulos conectando puntos a puntos y formando segmentos. Sin embargo, no queremos simplemente cualquier triangulación. Para producir el mejor resultado, necesitamos un triangulación que maximice el ángulo más pequeño en todos esos triángulos.

En la primera línea habrán dos enteros $n$ y $m$. $n$ representa el número de puntos que forman el borde, y $m$ es el número de puntos dentro de este. Puedes asumir que $n + m \leq 50$. Nota que los puntos dentro del borde pueden estar exactamente sobre el borde. La siguiente línea contendrá $2n$ enteros $x_1, y_1, x_2, y_2, ..., x_n, y_n$ separados por espacios en blanco, representando el borde $(x_1, y_1), ..., (x_n, y_n)$ en orden en contra de las manecillas del reloj. Finalmente habrán $2m$ enteros en la última línea en el mismo formato, representando los puntos dentro del borde o sobre el borde. Todas las coordenadas están en el rango $-100$ a $100$.