Un prado para mis ovejas
Lo habías repetido tantas veces que tu familia y amigos no te tomaban en serio. De tanto decirlo pero luego no hacerlo, tu "algún día lo dejo todo, me compro un terreno y me hago pastor" había pasado a ser un comentario anodino que nadie creía.
Pero el último año ha sido tan malo, con tanto estrés, tanto trabajo, tantas discusiones, tanto hastío y agotamiento que un día, después de decirlo por enésima vez, nació en tu interior la imperiosa necesidad de cumplirlo.
Y hete aquí, que después de buscar a escondidas en distintas páginas rurales, ya eres el flamante propietario de un terreno esperando sus ovejas.
El lugareño que te lo ha vendido te ha dicho que las lindes de tu nueva adquisición la marcan los árboles y se ha marchado con tu dinero. Ante tan mala educación y ausencia de información has decidido hacerle caso… hasta cierto punto. Vas a cercar el terreno lo más pequeño posible que incluya todos los árboles, pero creando también la forma con el menor número de lados posible. Seguro que eso te trae enemistades con los vecinos, pero puedes culpar al que te vendió el terreno.
Entrada
La entrada está formada por distintos casos de prueba, cada un ocupando dos líneas.
La primera línea de cada caso contiene el número de árboles que hay en el terreno (al menos 3 y como mucho 300.000). En la línea siguiente aparece una pareja de números por cada árbol con las coordenadas en las que se encuentran (x, y, ambas números naturales no mayores que 106). No habrá dos árboles en la misma posición.
Tras el último caso de prueba aparece una línea con un 0.
Salida
Por cada caso de prueba se escribirá el área total del terreno adquirido, sabiendo que es la menor posible que incluye a todos los árboles y, al mismo tiempo tiene la menor cantidad posible de lados.
Entrada de ejemplo
4 1 1 10 0 0 10 10 10 6 0 0 10 0 0 10 2 2 4 4 5 5 5 1 0 0 1 1000000 0 0 1000000 1000000 1000000 0
Salida de ejemplo
90 50 999999999999.5