Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
2 次元平面上の原点に高橋君がいます。
高橋君が 1 歩歩くと、いまいる点からのユークリッド距離がちょうど R であるような点に移動することができます(移動先の座標が整数である必要はありません)。これ以外の方法で移動することはできません。
高橋君が点 (X,Y) に到達するまでに必要な歩数の最小値を求めてください。
なお、点 (x_1,y_1) と点 (x_2,y_2) のユークリッド距離は \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} で与えられます。
制約
- 1 \leq R \leq 10^5
- 0 \leq X,Y \leq 10^5
- (X,Y) \neq (0,0)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
R X Y
出力
高橋君が (X,Y) に到達するまでに必要な歩数の最小値を出力せよ。
入力例 1
5 15 0
出力例 1
3
(0,0) \to (5,0) \to (10,0) \to (15,0) と 3 歩で到達できます。 2 歩以下で到達することはできないのでこれが最小です。
入力例 2
5 11 0
出力例 2
3
例えば (0,0) \to (5,0) \to (8,4) \to (11,0) と移動すれば良いです。
入力例 3
3 4 4
出力例 3
2
例えば (0,0) \to (2-\frac{\sqrt{2}}{2}, 2+\frac{\sqrt{2}}{2}) \to (4,4) と移動すれば良いです。
Score : 300 points
Problem Statement
Takahashi is standing at the origin of a two-dimensional plane.
By taking one step, he can move to a point whose Euclidian distance from his current position is exactly R (the coordinates of the destination of a move do not have to be integers). There is no other way to move.
Find the minimum number of steps Takahashi has to take before reaching (X, Y).
We remind you that the Euclidian distance between points (x_1,y_1) and (x_2,y_2) is \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}.
Constraints
- 1 \leq R \leq 10^5
- 0 \leq X,Y \leq 10^5
- (X,Y) \neq (0,0)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
R X Y
Output
Print the minimum number of steps Takahashi has to take before reaching (X, Y).
Sample Input 1
5 15 0
Sample Output 1
3
He can reach there in three steps: (0,0) \to (5,0) \to (10,0) \to (15,0). This is the minimum number needed: he cannot reach there in two or fewer steps.
Sample Input 2
5 11 0
Sample Output 2
3
One optimal route is (0,0) \to (5,0) \to (8,4) \to (11,0).
Sample Input 3
3 4 4
Sample Output 3
2
One optimal route is (0,0) \to (2-\frac{\sqrt{2}}{2}, 2+\frac{\sqrt{2}}{2}) \to (4,4).