C. Road roller

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:
  • no need to roll forth and back over the same spot: a single roll results in a completely flat surface, at the level specified by the user (EZRoller is heavy)
  • cutting edge 3000 BHP power plant (EZRoller is fast)
  • there is a button to start, stop, and turn (EZRoller is very user friendly)
   An early predecessor of EZRoller
http://searcharchives.vancouver.ca/ steam-roller-and-crew-at-corner-of-fleming-and-gibson-roads

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.

Input

Lines of X Y pairs for each point that needs to be levelled (X and Y are integers).

Output

The task is to define a line of connected segments by their endpoints such that it covers all the points given in the input and the number of segments is minimal.

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

This is a scaled problem and the real score is 
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.

Example input

1 5
2 2
3 4
4 1
4 4
5 1
5 3
5 5

Example output

4 1
3 1
3 5
1 5
1 1
5 5
5 1
So (4, 1) is connected to (3, 1), (3, 1) is connected to (3, 5) and so on. This gives a path of 6 segments.