Irrigando los Campos
Debido a escases de lluvias, el Granjero Juan quiere construir un sistema de irrigación para enviar agua entre sus campos .
Cada campo está descrito por un punto distinto en el plano 2D, con . El costo de construir una tubería de agua entre dos campos y es igual al cuadrado de la distancia euclidiana entre ellos:
A GJ le gustaría construir un sistema de tuberías de costo mínimo de tal manera que todos sus campos estén conectados – de tal manera que el agua de cualquier campo pueda seguir una secuencia de tuberías para llegar a cualquier otro campo.
Desafortunadamente, el contratista que está ayudando a GJ a instalar el sistema de irrigación se rehúsa a instalar cualquier tubería a menos que su costo (distancia euclidiana al cuadrado) sea al menos . Por favor, ayude a GJ a calcular la cantidad mínima que tendrá que pagar para conectar todos sus campos con una red de tuberías.
Entrada
- Línea 1: Los enteros y .
- Líneas 2…1+N: La línea contiene los enteros y .
Ejemplo de Entrada
3 11
0 2
5 0
4 3
Detalles de la Entrada
Hay campos, en las posiciones y . El contratista instalará únicamente tuberías que cuesten al menos .
Salida
- Línea 1: El costo mínimo para una red de tuberías que conecte todos los campos o si no se puede construir tal tubería.
Ejemplo de Salida
46
Detalles de la Salida
GJ no puede construir una tubería entre los campos y , pues sus costo sería únicamente . Por lo tanto, él construye una tubería entre y con costo y una tubería entre y con costo .
Comments