Irrigando los Campos


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Swift, VB

Debido a escases de lluvias, el Granjero Juan quiere construir un sistema de irrigación para enviar agua entre sus N campos (1 \leq N \leq 2000).

Cada campo está descrito por un punto distinto (x_i, y_i) en el plano 2D, con 0 \leq x_i, y_i \leq 1000. El costo de construir una tubería de agua entre dos campos i y j es igual al cuadrado de la distancia euclidiana entre ellos:

(x_i - x_j)^2 + (y_i - y_j)^2

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 C (1 \leq C \leq 1 000 000). 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 N y C.
  • Líneas 2…1+N: La línea i+1 contiene los enteros x_i y y_i.

Ejemplo de Entrada

3 11
0 2
5 0
4 3

Detalles de la Entrada

Hay 3 campos, en las posiciones (0, 2), (5, 0) y (4, 3). El contratista instalará únicamente tuberías que cuesten al menos 11.

Salida

  • Línea 1: El costo mínimo para una red de tuberías que conecte todos los campos o -1 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 (4, 3) y (5, 0), pues sus costo sería únicamente 10. Por lo tanto, él construye una tubería entre (0, 2) y (5, 0) con costo 29 y una tubería entre (0, 2) y (4, 3) con costo 17.


Comments

There are no comments at the moment.