CF336B.Vasily the Bear and Fly
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
One beautiful day Vasily the bear painted 2_m_ circles of the same radius R on a coordinate plane. Circles with numbers from 1 to m had centers at points (2_R_ - R, 0), (4_R_ - R, 0), ..., (2_Rm_ - R, 0), respectively. Circles with numbers from m + 1 to 2_m_ had centers at points (2_R_ - R, 2_R_), (4_R_ - R, 2_R_), ..., (2_Rm_ - R, 2_R_), respectively.
Naturally, the bear painted the circles for a simple experiment with a fly. The experiment continued for _m_2 days. Each day of the experiment got its own unique number from 0 to _m_2 - 1, inclusive.
On the day number i the following things happened:
- The fly arrived at the coordinate plane at the center of the circle with number
(
is the result of dividing number x by number y, rounded down to an integer). - The fly went along the coordinate plane to the center of the circle number
(
is the remainder after dividing number x by number y). The bear noticed that the fly went from the center of circle v to the center of circle u along the shortest path with all points lying on the border or inside at least one of the 2_m_ circles. After the fly reached the center of circle u, it flew away in an unknown direction.
Help Vasily, count the average distance the fly went along the coordinate plane during each of these _m_2 days.
一个美好的日子里,维克多熊在坐标平面上画了 2m 个半径均为 R 的圆。编号为 1 到 m 的圆,其中心坐标分别为 (2R−R,0)、(4R−R,0)、…、(2Rm−R,0);编号为 m+1 到 2m 的圆,其中心坐标分别为 (2R−R,2R)、(4R−R,2R)、…、(2Rm−R,2R)。
显然,熊画这些圆是为了进行一项关于一只苍蝇的简单实验。该实验持续了 m2 天。实验中的每一天被赋予一个从 0 到 m2−1(含)的唯一编号。
在编号为 i 的这一天,发生以下事件:
- 苍蝇抵达坐标平面,落点为编号为 ⌊mi⌋+1 的圆的圆心(其中 ⌊yx⌋ 表示将 x 除以 y 后向下取整所得的整数)。
- 苍蝇沿坐标平面飞向编号为 imodm+1 的圆的圆心(其中 xmody 表示 x 除以 y 后所得的余数)。熊注意到:苍蝇从编号为 v 的圆的圆心出发,沿最短路径飞至编号为 u 的圆的圆心,且该路径上所有点均位于至少一个(共 2m 个)圆的边界上或内部。苍蝇抵达编号为 u 的圆的圆心后,便朝未知方向飞离。
请帮助维克多计算:在这 m2 天中,苍蝇每天在坐标平面上飞行的平均距离。
输入格式
The first line contains two integers m, R (1 ≤ m ≤ 105, 1 ≤ R ≤ 10).
第一行包含两个整数 m 和 R(1≤m≤105,1≤R≤10)。
输出格式
In a single line print a single real number — the answer to the problem. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6.
在一行中输出一个实数——该问题的答案。若答案的绝对误差或相对误差不超过 10−6,则视为正确。
输入输出样例
输入#1
1 1
输出#1
2.0000000000
输入#2
2 2
输出#2
5.4142135624
说明/提示

Figure to the second sample

第二个样例对应的图
输入解题思路,AI测评打分。不知道怎么写?