Solved by 271 users: ...
UserDateAttemptTimeCMSC
zulo`21 mar 2008`Java200.28589
BaurKZ`24 apr 2010`Java1500.35610
dragonghy`03 apr 2007`FPC100.01631
zhangbjb`21 mar 2008`FPC600.01631
zhangbjb`21 mar 2008`FPC700.01631
zhangbjb`21 mar 2008`FPC800.01631
zhangbjb`21 mar 2008`FPC900.01639
david_it21`22 apr 2008`Ruby200.02644
Yagi_Arthur`22 dec 2009`FPC300.02657
Moonlight`13 dec 2007`FPC800.01662
fetetriste`03 dec 2008`Java500.29668
LiuChenheng`27 jul 2009`C++1300.01674
shouhm`28 mar 2008`C++100.01684
 C++ 164 FPC 63 Kylix 18 C 15 Java 14 Ruby 1 Perl 1
` >  >  >  >  >  >  >  >  >  > `

Time limit = 5 seconds

There is an island populated by robots. Robots live in isolated towns and communicate wirelessly.

Recently robots found that their economics is rather good and they may start traveling over the island, seeing different places and robots. In fact they just start feeling taste of life.

Robot-inventors discover very efficient and cheap transport, but for one restriction all roads should be straight lines connecting two towns.

Robot's economics is not so good to build road between every two towns. Besides there are ditches that roads can't cross.

They want to build system of roads that allows traveling from any town to any another town and besides has minimum possible total length.

Help them. They can't solve the problem without your help, because they start feeling and forget all the classic algorithms. (If fact they do not want to waste their energy on algorithms)

Think of towns as points. Think of roads and ditches as segments. Ends of any road should be towns.

Input The first line contains number of towns N and number of ditches M. N, M ≤ 200.

Then N lines follow with town description. Each line contains town name (word of length 20 characters of less) and two coordinates of the town:

Then M lines follow. Each line contains four numbers — coordinates of the first and second end of the ditch:

All coordinates are integers and their absolute values are less than 100 000.

Output If there is possibility to build roads connecting all towns together, then output line with 'YES'. The second line should contain number of roads R and next R lines should describes roads: each line should contain two town names.

If ditches do not allow building roads, then output one line with 'NO'.

 Input#1```2 1 Moscow 0 0 Kiev 2 0 1 -1 1 1 ``` Output#1```NO ```
 Input#2```3 1 Moscow 0 0 Kiev 2 0 Volgograd 1 2 1 -1 1 1 ``` Output#2```YES 2 Moscow Volgograd Volgograd Kiev ```

Author:
Voroztsov Artem
18 February 2003

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 200ms