На плоскости находятся n жуков. Каждый жук сидит в какой-то целочисленной точке (при этом более одного жука может находиться в одной и той же точке). Жуки хотят собраться на окружности с центром в начале координат (точке (0,0)) и радиусом R таким образом, чтобы расстояние между любыми двумя соседними по кругу жуками было одинаковым (то есть разместиться в вершинах правильного n-угольника). Для этого все жуки одновременно начинают движение к намеченной точке со скоростью 1 (если два жука встречаются в пути, то один просто облетает другого, не теряя при этом времени). За какое наименьшее время жуки смогут расставиться требуемым образом?
Формат ввода
Первая строка входных данных содержит два целых числа n и R — количество жуков и радиус круга соответственно (3 ≤ n ≤ 200, 1 ≤ R ≤ 100).
Каждая из последующих n строк содержит по два целых числа x_i и y_i — первоначальные координаты очередного жука (0 ≤ |x_i|, |y_i| ≤ 100). Несколько жуков могут находиться в одной точке; жуки также могут находиться в точке (0,0).
Формат вывода
Выведите наименьшее время, за которое жуки смогут расставиться в вершинах правильного n-угольника, вписанного в окружность радиуса R. Ответ выведите с абсолютной или относительной погрешностью не хуже 10^(-6).
Пример 1
Ввод
3 2
0 0
0 0
0 0
Вывод
2.00000000
Пример 2
Ввод
3 5
5 0
0 5
5 5
Вывод
6.08761429
Как я пытался решить эту задачу: давайте поставим одну из вершин данного вписанного многоугольника в точку (0;R), и пусть эта точка будет первой точкой многоугольника. То, насколько быстро доберутся жуки до своих точек - зависит от угла поворота многоугольника. Мы ищем наименьшее время, то есть нам надо минимизировать максимальное время добегания жука до его точки. Его можно будет перебрать от 0 до 360 / n. Так как при угле 360/n многоугольник будет повернут также, как и при повороте на 0 градусов, только первая вершина будет стоять на месте второй, вторая на месте третьей, и так далее. Значит мы можем составить функцию, зависящую от угла поворота n-угольника, возвращающую максимальное время добегания жука при оптимальном разбиении точек. И потом найти ответ, найдя локальный минимум функции с помощью бинарного поиска по производной. Проблема в том, что я никак не могу придумать как нам оптимально распределить жуков по точкам. По сути мы можем представить жуков и точки, как двудольный граф и нам нужно найти полное паросочетание с как можно меньшим максимальным ребром в данном паросочетании, где вес ребра - расстояние от жука до точки многоугольника.
typedef long double ld;
const ld pi = acos(-1.0);
vector<Point> polygon;
// расстояние между двумя точками
ld dist(Point first, Point scnd) {
return sqrtl((scnd.x - first.x) * (scnd.x - first.x) + (scnd.y - first.y) * (scnd.y - first.y));
}
// построение n-угольника
void build_polygon(ld angle) {
polygon = { { 0, radius } };
ld f0 = pi / 2;
for (int i = 1; i < n; i++) {
polygon.push_back({ radius * cos(f0 + angle * i),
radius * sin(f0 + angle * i)});
}
}
// подсчет координат точки после поворота на угол
// угол нужно передавать отрицательный, потому что в радианах считается угол против часовой стрелки
// а мы поворачиваем по часовой стрелке
Point rotate(Point a, ld angle) {
return { a.x * cos(angle) - a.y * sin(angle), a.x * sin(angle) + a.y * cos(angle) };
}
Также я думал над тем, что данную функцию можно формализовать так:
Есть матрица A, в которой в i-ом столбце, j-ой строке лежит расстояние от i-ого жука, до j-ой точки n-угольника
и надо выбрать в каждой строке по одному числу так, чтобы максимум из данных чисел был как можно меньше, причем из каждого столбца можно выбрать только одно число.
Подскажите пожалуйста, какие есть идеи по решению? Может быть я делаю что-то неверно? Спасибо!
P.S. Венгерский алгоритм сюда не подойдет, он оптимизирует сумму, а надо оптимизировать максимум
Простой
Средний
