Help Mr Jones to enjoy his bicycle round-trip Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his holidays. As he really loves cycling, the length of his route is completely irrelevant, but he dislikes to drive around the landscape without a target. The route he likes is from on city in a straight line to another, without any detour.

As Mr Jones is a passionated code golfer, he wants you to find a program, that plans a round trip for him, given a set of cities. The input has the form A (B|C). A is a city's name, B and C are its coordinates. You may assume, that the coordinate are positive and less than 1000. The data sets for the cities are line-separated. Here is an example, of how an example input might look like:


SomeTown (1|10)
ACity (3|4)
Wherever (7|7)
Home (5|1)


Mr Jones isn't pedantic, he just wants to have a useful program. Thus, you may decide by your self how the output is looking like, as long as it mets these criteria:


The output is a map of the cities, with the route drawn between them. If anything is correct, the route shouldn't overlap itself and should end where it started
The coordinates are like in usual programming: (1|1) is in the NW corner. Add kind of a ruler to the maps border, to ease reading it
The cities names have to be written down on the map, but feel free to use abbreviations which is explained somewhere else on the map
The map can be both ASCII-art or an image
Keep the output readable


An output might look like this:


  1234567
 1    D  
 2   * * 
 3  *  * 
 4  B   *
 5  *   *
 6  *   *
 7 *    C
 8*   ** 
 9*  *   
10A**

A: SomeTown
B: ACity
C: Wherever
D: Home


The program with the smallest char count wins. I don't count parameters to the compiler / interpreter, if they are needed for compiling, but please don't abuse this rule. Usual code golf rules apply.

Here is another testcase. You output doesn't have to match mine, nor do you have to choose the same path as me. The output is drawn by hand and shows a possible output. Input:


home (5|7)
supermarket (13|12)
park (15|5)
new plaza (9|16)
friend's house (20|11)
old castle (14|21)
riverside (1|20)
beach (10|1)
cinema (21|18)
forest (23|7)
little island (21|1)
museum of code-golf (6|25)
airport (18|25)
tea-shop (24|14)
restaurant (24|22)
great bridge (3|12)
SO building (25|9)


And this is an example output:


           1111111111222222
  1234567890123456789012345
 1         H*        *K    
 2        *  *      *  *   
 3        *   *    *   *   
 4       *     * **    *   
 5      *       C      *   
 6     *               *   
 7    A                 J  
 8   *                   *  
 9   *                    Q
10   *                    *
11   *            ***E    *
12  P         B***   *   * 
13  *        *       *   * 
14  *       *        *   N 
15 *       *          *  * 
16 *      D           *  * 
17 *       *          *  * 
18*         *         I  * 
19*          *        *  * 
20G           *      *   * 
21 *           F     *   *
22  *         **    *    O 
23   *      **     *   **  
24    *   **       *  *    
25     L**         M**

A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building


I am not an English native speaker. Feel free to correct my language and grammar, if necessary.
Haskell, 633 characters

import List
c n=n&gt;&gt;=(++" ").show.(*3)
(x&amp;y)l="&lt;text x='"++c[x]++"' y='"++c[y]++"'&gt;"++l++"&lt;/text&gt;"
f%p=[a-1,b+2,(a+b)/2]where n=map(f.fst)p;a=minimum n;b=maximum n
s p=concat["&lt;svg xmlns='http://www.w3.org/2000/svg' viewBox='",c[i,m-1,j,n],"'&gt;&lt;polygon fill='none' stroke='#c8c' points='",c$snd=&lt;&lt;(sort$map a p),"'/&gt;&lt;g font-size='1' fill='#bbb'&gt;",(\x-&gt;(x&amp;m$show x)++(i&amp;x$show x))=&lt;&lt;[floor(i`min`m)..ceiling(j`max`n)],"&lt;/g&gt;&lt;g font-size='2'&gt;",snd=&lt;&lt;p,"&lt;/g&gt;&lt;/svg&gt;"]where a((x,y),_)=(atan2(x-q)(y-r),[x,y]);[i,j,q,m,n,r]=fst%p++snd%p
w(l,s)=((x,y),(x&amp;y)l)where(x,r)=v s;(y,_)=v r
v=head.reads.tail
main=interact$s.map(w.break(=='(')).lines


Rather longish for code-golf, but produces a lovely SVG map:


Or, if your browser can't handle SVG, a PNG of that image:





Edit: (648 -> 633) in-line coordinate drawing, and possibly draw more than needed, letting them be clipped by the viewBox; also a few golf-tricks here and there.