Helicópteros entre islas
El archipiélago de Byteland consta de
La administración quiere comprar helicópteros para transportar los habitantes entre las islas. Un helicóptero podrá proporcionar una ruta entre dos islas en la distancia mínima obtenida horizontal o verticalmente (paralela a los ejes de coordenadas). Además, debido a la capacidad del tanque, dicha ruta no puede exceder un valor
La inversión debe cumplir las siguientes condiciones:
El número de helicópteros comprados será mínimo.
El número de parejas de islas entre las que se puede realizar el transporte utilizando uno o más helicópteros debe ser máximo.
La cantidad de la longitud de todas las rutas es mínima.
Tarea
Escriba un programa que, conociendo los valores de
el número mínimo de helicópteros que comprará la administración;
Número de parejas de islas no reguladas entre las que se puede realizar el transporte en helicóptero directa o indirectamente.
La suma de las distancias recorridas por todos los helicópteros comprados (la distancia recorrida por un helicóptero es la distancia entre las islas entre las cuales se transporta).
Entrada
La entrada contiene en la primera línea un valor
En la segunda línea los números naturales
Salida
Si el valor de
Si el valor de
Si el valor de
Restricciones y aclaraciones.
•
•
• Las coordenadas de los picos de las islas son números naturales
• dos islas cualesquiera no tienen puntos comunes;
• en el requisito
• La distancia entre dos islas también puede ser un número real. En el Requisito
• Para calcular y mostrar un número real
• Para la correcta resolución del requisito
• Para la correcta resolución del requisito
• Para la correcta resolución del requisito
Ejemplo de Entrada #1
1
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30
Ejemplo de Salida #1
3
Explicación:
Los datos corresponden a las cifras anteriores:
Parejas de islas con transporte directo en helicóptero:
Ejemplo de Entrada #2
2
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30
Ejemplo de Salida #2
4
Explicación:
Los datos corresponden a las cifras anteriores:
Parejas de islas con transporte directo en helicóptero:
La isla
Ejemplo de Entrada #3
3
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30
Ejemplo de Salida #3
30
Explicación:
Los datos corresponden a las cifras anteriores:
Parejas de islas con transporte directo en helicóptero:
La isla
Los helicópteros proporcionan transporte directo entre las islas:
En total, las líneas navieras tienen una distancia de
Comments
easy
La salida se dará en caso de ser real con 10 dígitos después de la coma.