CF 287(div 2) B Amr and Pins

解题思路：一开始自己想的是找出每一次旋转所得到的圆心轨迹，将想要旋转到的点代入该圆心轨迹的方程，如果相等，则跳出循环，如果不相等，则接着进行下一次旋转。后来看了题解，发现，它的旋转可以是任意角度的，所以旋转后的圆心应该在一个区域，而没有固定的圆心轨迹的方程。

如图所示，设c0为最初给出的圆，令圆c0绕O1点旋转，则对于绕O1点这一点的旋转来说，c1为其旋转后所得到的圆心轨迹，则可以看到，通过1次旋转后，距离最近为0,距离最远为线段OO2=2r,

对于第二次旋转，选取O2为圆心，作圆，再令圆c2绕O3旋转，得到圆心的轨迹为c3，离O点最近为OO2=2r,最远为OO4=4r

所以推出一般结论，令想要旋转到的点到起始的圆心的距离为d, 那么旋转次数为d/2r,这里的四舍五入用进1法（不能舍去，所以用ceil函数）

B. Amr and Pins

Amr loves Geometry. One day he came up with a very interesting problem.

Amr has a circle of radius r and center in point (x, y). He wants the circle center to be in new position (x', y').

In one step Amr can put a pin to the border of the circle in a certain point, then rotate the circle around that pin by any angle and finally remove the pin.

Help Amr to achieve his goal in minimum number of steps.

Input

Input consists of 5 space-separated integers r, x, y, x' y' (1 ≤ r ≤ 10⁵, - 10⁵ ≤ x, y, x', y' ≤ 10⁵), circle radius, coordinates of original center of the circle and coordinates of destination center of the circle respectively.

Output

Output a single integer — minimum number of steps required to move the center of the circle to the destination point.

Sample test(s)

input

2 0 0 0 4

output

input

1 1 1 4 4

output

input

4 5 6 5 6

output

Note

In the first sample test the optimal way is to put a pin at point (0, 2) and rotate the circle by 180 degrees counter-clockwise (or clockwise, no matter).

#include<stdio.h>

#include<math.h>

int main()

{

	double i,r,x0,y0,x1,y1;

	scanf("%lf %lf %lf %lf %lf",&r,&x0,&y0,&x1,&y1);

	double dist=sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));

	printf("%.0lf\n",ceil(dist/(2*r)));

}

巴特西

CF 287(div 2) B Amr and Pins

最新文章

热门文章