Олимпиадный тренинг

Задача . Watering the Fields


Задача

Темы: Минимальный каркас

В связи с недостатком дождей Фермер Джон хочет построить ирригационную систему для доставки воды на N его полей (1 <= N <= 2000).
Все поля описываются различными точками (xi,yi) на плоскости, где 0<=xi,yi<=1000. Цена постройки трубы для доставки воды из точки i в точку j равна квадрату евклидового расстояния между ними:
(xi - xj)^2 + (yi - yj)^2
ФД хочет проложить минимальную по стоимости систему труб так, чтобы все его поля были соединены таким образом, чтобы водя из любого поля могла достичь любого другого поля по некоторой последовательности из проложенных труб.
К несчастью, подрядчик, у которого ФД заказал эту систему, отказывается прокладывать трубы стоимостью меньше чем C (1 <= C <= 1,000,000).
Пожалуйста, помогите ФД определить минимальное количество денег, которые ФД должен заплатить, чтобы проложить задуманную систему труб.
PROBLEM NAME: irrigation
Формат входных данных
* Строка 1: Целые числа N и C.
* Строки 2..1+N: Строка i+1 содержит целые числа xi и yi.
Формат выходных данных
* Строка 1: Минимальная стоимость задуманной сети труб , или -1 если такая сеть не может быть построена.
Примечание
ФД не может построить трубу между полями в точках (4,3) и (5,0), поскольку её стоимость не более 10. Поэтому он построит трубы между (0,2) и (5,0) со стоимостью 29 и трубу между (0,2) и (4,3) со стоимостью 17.
Примеры
№Входные данныеВыходные данные
1 
3 11
0 2
5 0
4 3
 
46
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет