bob.txt

Welcome...
You have been assigned the task of developing a solver to help route a Printed Circuit Board.
In this case each circuit board will have a set termination points for a trace (or antenna points) and an originating point (or feed points) on the board.

You will be presented with a set of boards of varying size and difficulty. Each board will have a dimension, a set of nulls (playes your trace cannot go), a feed point, and a set of antenna points.

Your goal is to have all traces start at the feed point and end at all the antenna points. The distance of these traces must be equal for all antenna points.
There can be no unterminated traces (they must start at a feed point and end at an antenna point), traces cannot cross over another trace.
Traces can split at any point. All traces must be connected.

The movement of a trace can be at 45 degree angles on the board.
Therefore traces can only go to neighboring points on the grid (up to 8 different locations).
The lengths of those traces will be calculated
 by adding all the trace lengths together (NOTE: A diagonal movement is length sqrt(2)) versus a horizontal/vertical movement length 1.



The grid coordinate system is setup so that X increases to the right and Y increases going down.
(0,0) is top left of the grid.
Points are sent as: X Y with 0 based indexing.

Here is an example with (Problem 1) with solution (Solution 1):

Problem 1
Dimensions 1
5 5
Feed 1
0 2
Antenna 4
0 0
0 4
4 0
4 4
Null 4
0 1
0 3
2 1
2 4


Solution 1
Line 3
Segment 0 2 2 2
Segment 0 0 4 4
Segment 0 4 4 0

Solutions must consist of the problem number (in this case 1) and the lines solving the solution: Solution <problem number>\n
Line <number of lines to follow>\n
Segment <start X pos> <start Y pos> <end X pos> <end Y pos>\n

Here we go! Here comes your first problem...

Problem 4
Dimensions 1
8 9
Feed 1
0 0
Antenna 4
3 3
3 7
5 5
7 5
Null 19
0 2
0 5
0 6
0 7
0 8
1 0
1 1
1 7
2 4
2 5
4 6
4 8
5 3
6 3
6 8
7 1
7 2
7 4
7 6