One of the factors slowing down operations at the IGG steel mill is
the uneven concrete surface of the factory yard where incoming raw
material is received and sorted. Fortunately
there's still time to use one of the brand new products of the company, the EZRoller
to get a flat surface. EZRoller looks like a traditional road roller but
has a number of advanced features:
Unfortunately these features impose a limitation on the path EZRoller can follow: it is not possible to turn without stopping, and the turn button allows turning only in 45 degree steps. Due to inertia, stopping and starting are very time consuming operations, so the operator of EZRoller is asked to avoid these whenever possible (it's much easier to rely on EZRoller's extreme strength and sturdiness, and "think outside the box", so to speak).
You need to find a short path for EZRoller for leveling all the points specified on the surface of the factory yard.
The segments can be vertical, horizontal or 45 degree diagonals. The endpoints of the segments should be given as X Y pairs in order, one per line (X and Y must be integers).
SCORE := round(100 * (1 - sqrt(1 - Kmin/K)))where K is the number of segments in the output and Kmin is the best submission so far.
1 5 2 2 3 4 4 1 4 4 5 1 5 3 5 5
4 1 3 1 3 5 1 5 1 1 5 5 5 1So (4, 1) is connected to (3, 1), (3, 1) is connected to (3, 5) and so on. This gives a path of 6 segments.