题目

Programming contests became so popular in the year 2397 that the governor of New Earck — the largest human-inhabited planet of the galaxy — opened a special Alley of Contestant Memories (ACM) at the local graveyard.
The ACM encircles a green park, and holds the holographic statues of famous contestants placed equidistantly along the park perimeter.
The alley has to be renewed from time to time when a new group of memorials arrives.
When new memorials are added, the exact place for each can be selected arbitrarily along the ACM, but the equidistant disposition must be maintained by moving some of the old statues along the alley.
Surprisingly, humans are still quite superstitious in 24th century:
the graveyard keepers believe the holograms are holding dead people souls, and thus always try to renew the ACM with minimal possible movements of existing statues (besides, the holographic equipment is very heavy). Statues are
moved along the park perimeter. Your work is to find a renewal plan which minimizes the sum of travel distances of all statues. Installation of a new hologram adds no distance penalty, so choose the places for newcomers wisely!

Input

The input file contains several test cases, each of them consists of a a line that contains two integer
numbers: n — the number of holographic statues initially located at the ACM, and m — the number
of statues to be added (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000). The length of the alley along the park perimeter
is exactly 10 000 feet.

Output

For each test case, write to the output a line with a single real number — the minimal sum of travel
distances of all statues (in feet). The answer must be precise to at least 4 digits after decimal point.
Note:
Pictures show the first three examples. Marked circles denote original statues, empty circles denote
new equidistant places, arrows denote movement plans for existing statues.

Sample Input

2 1
2 3
3 1
10 10

Sample Output

1666.6667
1000.0
1666.6667
0.0

题解

原本有 n 个东西在圆周上平均分配,再多 m 个, 求最少需要移动的距离

画下图很容易找到关系
将最上面当作原点,所有点从原点开始按间距摆放

每个点应该移动到与其最接近的点上,由于平均分配,并且是增加数量,因此新的图里,点会更加密集,这就保证了不会有有一个新位置同时是两个老位置的最近位置

只需要找到每个位置最近的新位置即可

最需要注意的是 double 造成的各种 浮点误差

结果最少输出 4 位精度,输出 6 位小数妥妥的

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const double eps = 1e-6;
const double l = 10000;

bool equal(double a,double b) {
    return fabs(a - b) < eps;
}
int toInt(double a) {
    return (int)(a + 0.001);
}

bool Do() {
    double n,m;
    if(!(cin >> n >> m))
        return false;

    m += n;

    double per = l / n;
    double newper = l / m;

    double ans = 0;
    for(int i = 0;i < n;i++) {
        double pos = i * per;
        double newpos = pos / newper;
        if(!equal(newpos,(double)(toInt(newpos)))) {
            int a = toInt(newpos);
            ans += min(fabs(pos - a*newper),fabs(pos - (a + 1)*newper));
        }
    }

    cout << fixed << setprecision(6) << ans << endl;
    return true;
}

int main() {
    while(Do());
    return 0;
}