17639번 - Tower Defense 서브태스크스페셜 저지다국어

You are playing a simple tower defense game.

The game is played on an infinite square grid. At the beginning of the game the entire grid is empty, except for two cells. The cell (x_e, y_e) contains the entrance through which enemy units will be entering the grid. The cell (x_h, y_h) contains your home: a building you are trying to protect from the invaders.

Before the invaders arrive you may build up to 10 000 turrets. Each turret will occupy one empty cell of the grid.

The invaders can move in four cardinal directions and always follow the shortest path from the entrance to your home. For your master plan, you require that distance to be exactly d.

The first line of input contains two integers: the coordinates x_e and y_e (−10⁹ ≤ x_e, y_e ≤ 10⁹).

The second line of input contains two integers: the coordinates x_h and y_h (−10⁹ ≤ x_h, y_h ≤ 10⁹).

The third line of input contains one integer: the desired distance d (1 ≤ d ≤ 2000).

The cells (x_e, y_e) and (x_h, y_h) are distinct and their distance on the empty grid is at most 2000.

If there is no solution, output a single line with the text “impossible” (quotes for clarity).

If there are multiple solutions, you may output any one of them. The first line of output should contain the number t of turrets you want to place (0 ≤ t ≤ 10 000). Each of the following t lines should contain the coordinates of one turret.

All coordinates of all turrets must be between −2 · 10⁹ and 2 · 10⁹, inclusive.

The checker for this task will also accept solutions that output additional and/or different whitespace between the numbers in the output.

In the first example the current distance from the entrance to your home is already 20. You cannot decrease it to 14 by placing turrets.

In the second example the invaders have to go around the turret at (10, 47) which increases the distance between the entrance and your home from 30 to 32. The second turret in this example output is useless and illustrates that you do not have to minimize the number of turrets, and that the turrets can be placed outside the part of the grid that contains the entrance and the exit.

The third example output is shown below, using E for the entrance, H for the home and asterisks for turrets.

.......
..*....
..*....
.E*.*H.
....*..
.....*.
.......