## 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: