ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2005 Round II

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Goat in the Garden 3

Time limit: 1.0 second
Memory limit: 64 MB
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.


-1 0
0 1
1 2
2 1
2 0
1 -1
0 -1
Problem Author: Aleksey Lakhtin
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005
To submit the solution for this problem go to the Problem set: 1368. Goat in the Garden 3