Сайт підготовки до олімпіади з інформатики

програмування в С++

Збирання мита PDF Печать E-mail
Добавил(а) Administrator   
26.09.12 00:00

Тестуюча система

http://ejudge.vippo.ua/cgi-bin/new-client?contest_id=1 (користувачі user3-user9, паролі 3-9)

Задача

Збирання мита (TALLAGE) -100 балів.

Король країни Аріїв завоював N міст на території сусідніх держав.

Тепер йому необхідно створити систему збирання мита з завойованих територій. Він хоче збудувати таку систему шляхів між цими містами, щоб до будь-якого міста можна було дістатися (можливо, через інші міста) зі столиці, але у воєнному стані на транспорт виділяється дуже незначна частина фінансів, тому сумарна вартість побудованих шляхів сполучення між містами має бути мінімальною.

Вхідні дані:

Перший рядок вхідного файлу містить натуральне число N (1≤N≤100) – кількість міст у країні, а також цілі числа X та Y – координати столиці.

Наступні N рядків містять через проміжок координати Xi , Yi завойованих міст.

Значення координат по модулю менші 50000.

Вихідні дані:

Єдиний  рядок має містити дійсне число з трьома знаками після коми – сумарну вартість побудованих доріг. Вважайте, що вартість одиниці довжини дороги дорівнює одній умовній одиниці.

Приклади:

 

TALLAGE.DAT

TALLAGE.SOL

6  0 0

1  1

-1  1

0  2

1 -1

-1 -1

0 -2

8.485

 

Статистика

Пользователей : 152
Статей : 222
Просмотрено статей : 90123

Вход/Регистрация

Нет