Los k-clústers sociales

Un alumno de Ingeniería Informática se ha leído un libro de Carl Jung y quiere hacer un estudio psicológico sobre las relaciones sociales y las dinámicas de grupo. En concreto, le interesan las relaciones entre las personas introvertidas y extrovertidas. Así que ha decidido hacer un experimento: ha reunido en una amplia sala a personas extrovertidas e introvertidas. Para estructurar el análisis, pensó que lo mejor era dividir a todos en grupos de 4 personas, donde 3 son introvertidas y 1 es extrovertida. Tras observar las dinámicas sociales durante el experimento, el investigador notó que las personas extrovertidas tienden a mantener cierto espacio personal mínimo entre ellas. En particular, nunca se observó que dos extrovertidos estuvieran extremadamente cerca el uno del otro, ya que esto generaba tensiones en la interacción social. Después de llevar a cabo este experimento y recoger todos los datos, el futuro psicólogo se puso con la fase de análisis. Tras pasar semanas buscando patrones, no consiguió nada. El investigador estaba a punto de abandonar la idea, hasta que pensó en analizar los datos de manera geométrica, y entonces todo empezó a tener sentido. Si imaginamos que las personas son puntos en el espacio bidimensional, se puede observar que los grupos se ordenan de tal manera que los tres introvertidos se separan del extrovertido, ubicándose todos exactamente a la misma distancia de él. Geométricamente hablando, el extrovertido actúa como el centro exacto de los tres introvertidos. Curiosamente, la dinámica de estas tríadas resultó ser tan equilibrada que el extrovertido siempre quedaba arropado espacialmente entre ellos, sin llegar a quedar nunca excluido fuera del perímetro social que formaban sus tres compañeros. Luego, notó que los grupos empezaron a unirse; es decir, las personas de grupos diferentes empezaron a relacionarse entre sí sin moverse de su sitio. Curiosamente, al observar las distancias, descubrió que para que se unan dos grupos, la distancia entre las personas extrovertidas de cada uno no tiene que superar una constante. El investigador denominó a estas macro-redes de personas conectadas como $k$-clústers. En su análisis, concluyó que las personas extrovertidas "se atraen entre sí" si están lo suficientemente cerca y, como son los líderes de sus subgrupos, los introvertidos también terminan formando parte del mismo $k$-clúster. Sin embargo, por ser un poco desordenado, el joven investigador ha perdido las coordenadas exactas de los extrovertidos y no encuentra cómo quedaron conformados los $k$-clústers al final del experimento. ## Entrada La entrada está compuesta por un único caso de prueba de varias líneas, empezando con un número entero $M$ y un número real $K$ ($1 \leq M \leq 100000$) ($1.0 \leq D \leq 1000.00$), donde $K$ es una constante de distancia máxima a partir de la cual se forma el $k$-clúster. Luego siguen $M$ líneas indicando las posiciones de los introvertidos de cada grupo, con la siguiente forma: $id$: $P1, P2, P3$ donde $id$ es el identificador del grupo y $Pi$ es un punto que representa la posición de una persona introvertida con coordenadas reales $x$, $y$ ($-10000.0 \leq x, y \leq 10000.0$). ## Salida La salida consiste en un único número con dos decimales de precisión: la máxima suma de las áreas de los grupos que conforman un mismo $k$-clúster. El área de un grupo corresponde al área de su envolvente convexa mínima.

4 4
1: 1 1 3 1 2 3
2: 2 6 4 5 2 4
3: 11 10 9 8 12 8
4: 9 1 10 3 11 1

4.00