<ПРЕД Задача:
СЛЕД>
Задачу решил 271 пользователь: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Остров прямых дорог

Time limit = 5 секунд

На некотором острове есть города и есть рвы, но совсем нет дорог.

На этом острове живут роботы, которые ходят только по прямым линиям и могут изменить своё направление только в городе.

Некоторые рвы мешают провести прямую дорогу между некоторыми городами.

Нужно построить дороги так, чтобы из любого города робот мог было попасть в любой другой.

Проверьте, можно ли это сделать и если можно, укажите, между какими городами нужно провести дорогу, чтобы суммарная длина дорог была минимальна.

Города — это точки, рвы и дороги — отрезки. Все дороги прямые и не имеют общих точек со рвами. Концы любой дороги должны быть городами.

Вход Первая строчка входа содержит количество городов N и количество рвов M разделенные пробелом. N, M ≤ 200.

Затем идет N строчек, в каждой из которых название города (слово из 20 или меньшего числа заглавных и прописных латинских букв без пробелов) и пара декартовых координат этого города, и M строчек, каждая из которых содержит четыре числа — координаты первого конца рва и второго конца рва. Все координаты целые числа по модулю меньше 100000.

Выход. Если можно построить доргоги, связывающие все города, то напишите в первой строчке 'YES'. Во второй строчке — количество дорог R, а в следующих R строчках — описание дорог, а именно, в каждой строчке названия двух городов через пробел, между которыми нужно провести дорогу.

Если невозможно свзязать все города в единую сеть, то выведите одну строчку, содержащую слово 'NO' без кавычек.

Вход#1
2 1
Moscow 0 0
Kiev 2 0
1 -1 1 1
Выход#1
NO

Вход#2
3 1
Moscow 0 0
Kiev 2 0
Volgograd 1 2
1 -1 1 1

Выход#2
YES
2
Moscow Volgograd
Volgograd Kiev

Автор:
Ворожцов Артем, ФИЗТЕХ олимпиада, февраль 2003ю
18 февраля 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 3.226.248.180