| Coding Cup TecNM 2025 |
|---|
| Закончено |
Resulta que la vida laboral es justo como la escuela, pero aún peor. Ahora en lugar de conectar routers en un salón de clase tu trabajo es conectar un montón de routers repartidos a través de una ciudad con calles perféctamente cuadradas. Para ello tienes que conectarlos con fibra óptica a través de postes y vías subterráneas; para propósitos prácticos supongamos que no importa por dónde los metas entre esas dos, pero lo importante es que no los metas a través de manzanas. Para tu conveniencia los routers siempre estarán en las esquinas de las manzanas.
Igual que en la escuela, lo importante es pasar. En este caso eso significa solo conectar los routers; redundancia y cosas por el estilo no importan.
Un número N, el número de routers a conectar.
En las siguientes N líneas, N pares de números xi, yi representando cada una de las coordenadas de los routers.
La mínima longitud de cable necesaria para conectar todos los routers.
3 5 7 1 1 2 8
12
Se puede conectar el router en la posición (1, 1) con el de la posición (2,8); estos están a distancia 8. Luego conectamos el (2, 8) con el (5, 7), y estos 2 están a dsitancia 4. La distancia total es 8 + 4 = 12.
| Название |
|---|


