题目链接:http://codeforces.com/problemset/problem/507/B
题目意思:给出圆的半径,以及圆心坐标和最终圆心要到达的坐标位置。问最少步数是多少。移动见下图。(通过圆上的边固定转动点,然后转动任意位置,圆心就会移动了,这个还是直接看图吧)
解题的思路就是,两点之间,距离最短啦~~~~要想得到最少步数,我们需要保证圆心在这条连线上移动,每次转动的角度是180度,而每步移动的距离是2r,直到两个圆交叉,要注意最后一步转动的角度可能会小于180度。最后就是注意精度啦,用天花板函数ceil()吧,否则精度会被舍弃,最后一步实质上根本没有算进去!~~~~更详细的解题思路请参考官方题解。
http://codeforces.com/blog/entry/15975
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; typedef __int64 ll; int main()
{
ll r, x, y, x1, y1;
while (cin >> r >> x >> y >> x1 >> y1) {
ll difx = (x-x1)*(x-x1);
ll dify = (y-y1)*(y-y1);
ll ans = ceil(sqrt(difx + dify) / (*r));
printf("%I64d\n", ans);
}
return ;
}