дам 30 баллов {Для изучения океана планеты Солярис было построено N исследовательских станций. Каждая из станций задаётся координатами (xi, yi, zi) в пространстве. Для быстрого перемещения между станциями запланировано построить N-1 телепорт, каждый из которых будет соединять две станции и позволит перемещаться между ними в произвольном направлении. Набор телепортов должен соединять все станции, то есть так, чтобы с любой станции до любой другой можно было переместиться либо непосредственно через соединяющий их телепорт, либо использовав несколько телепортов с посещением произвольных станций. Стоимость постройки телепорта между станциями i и j равна cij = min(|xi – xj|, |yi – yj|, |zi – zj|).

Напишите программу, которая по положению N исследовательских станций поможет найти минимальную стоимость искомого набора телепортов.

Вход: файл input.txt, в первой строке содержится число N – количество исследовательских станций. В следующих N строках содержится описание очередной станции, задаваемой координатами (xi, yi, zi). Координаты разделяются пробелом.

Ограничения: 2≤N≤105, -109≤ xi, yi, zi ≤109

Выход: файл output.txt, в единственной строке содержится число – минимальная стоимость постройки набора телепортов.}Язык C++
Please enter comments
Please enter your name.
Please enter the correct email address.
You must agree before submitting.

Answers & Comments


Copyright © 2025 SCHOLAR.TIPS - All rights reserved.