Contest Duration: - (local time) (100 minutes) Back to Home
Official

## C - Compass Walking Editorial by en_translator

Let $$d$$ be the Euclidean distance from the origin to $$(X,Y)$$. The answer is:

• $$1$$ if $$d = R$$
• $$2$$ if $$d \neq R$$ and $$d \leq 2R$$
• $$\lceil \frac{d}{R}\rceil$$ otherwise

The first case is obvious.

For the third case, assuming the second case is true, we can see that we can reach in $$\lceil \frac{d}{R}\rceil$$ steps, since we can “move straight towards the destination until the remaining distance is no more than $$2R$$, and then use two steps to reach the destination (based on case 2).”

Now let us consider the second case.

The strict proof is as follows.

Proof Let $$P$$ be the destination. There exists a point $$Q$$ on the perpendicular bisector of the origin and $$P$$ such that the distance from the origin is $$R$$. We can move to $$Q$$ in the first step, then move to $$P$$ in the second.

A more intuitive explanation is as follows.

Assume $$R = 2$$. Takahashi can move to any point on the red circle in the diagram below.

If he use the first step to move to $$(2, 0)$$, he can use the second step to move to any point on the blue circle centered at $$(2, 0)$$.

If he use the first step to move to $$(\sqrt{2}, \sqrt{2})$$, he can use the second step to move to any point on the blue circle centered at $$(\sqrt{2},\sqrt{2})$$.

Like this way, one can fill the region inside the circle of radius $$2R$$ centered at the origin by drawing circles of radius $$R$$ centered at each point on the red circle.

Sample Code (Python)

import math

R,X,Y=map(int,input().split())
D=math.sqrt(X*X+Y*Y)

if D==R:
print(1)
elif D<=R+R:
print(2)
else:
print(math.ceil(D/R))


posted:
last update: