How do you let your goat walk around your vegetable garden? That becomes a real problem sometimes.
You should make sure the goat doesn't die of starvation, and you certainly don't want all your crops to
be eaten. The garden is a field consisting of 1 × 1 square elements. You can build a fence in some of the
garden's elementary squares. To feed itself, the goat needs to eat all the crops in the area consisting of
K (1 ≤ K ≤ 106) squares. The goat initially stands in the point of origin (i.e. in the square with
coordinates (0, 0)). You have to put the fence in the minimum number of squares so that the goat will be
able to visit exactly K squares. The area is said to be fenced if it is impossible to leave it moving only in
horizontal or vertical directions.
The input stream contains one number K — the total area granted to the goat.
The first line shall contain the amount N of boundary (fenced) squares. Each of the following N lines
shall contain two numbers — X and Y coordinates of the fenced square, respectively. Squares should be
output in the order of traversal.
Problem Author: Aleksey Lakhtin
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005