0086. Two Queens and The King

Input file name: 2queens.in
Output file name: 2queens.out
Time limit: 5 s
Memory limit: 64 megabytes

Two players, White and Black, are playing on the infinite chessboard. There are two white queens and one black king on the board. White wants to checkmate the black king as soon as possible, while Black tries to avoid it.

Sides make their moves in turn – first White moves one of his queens, then Black moves his king.

Your task is to find the minimal number of White's moves that he needs to checkmate the black king.

Input file

The input file contains coordinates x1 y1 x2 y2 xK yK, separated by spaces. All coordinates are integers with absolute value not greater than 108. The input position is correct. White moves first.

Output file

The first line is to contain minimal possible number of White's moves leading to victory. The second line contains one of the optimal moves n x y, where n is the number of moving queen (1 or 2), and x and y are coordinates to which this queen should move (not greater than 109 by an absolute value). If it is not possible to checkmate the black king, output single -1.

It is guaranteed that all test case positions have solution with both coordinates not greater that 109 by an absolute value.

Examples:

2queens.in2queens.out
0 0 4 0 1 21 2 2 2


Source: Petrozavodsk Winter 2003. Final Contest, Saturday, February 08

Discuss       Submit a solution



Printable version