Задача на геометрию
Ограничение по времени: 2 секунды
На плоскости находятся n жуков. Каждый жук сидит в какой-то целочисленной точке (при этом более одного жука может находиться в одной и той же точке). Жуки хотят собраться на окружности с центром в начале координат (точке (0,0)) и радиусом R таким образом, чтобы расстояние между любыми двумя соседними по кругу жуками было одинаковым (то есть разместиться в вершинах правильного n-угольника). Для этого все жуки одновременно начинают движение к намеченной точке со скоростью 1 (если два жука встречаются в пути, то один просто облетает другого, не теряя при этом времени). За какое наименьшее время жуки смогут расставиться требуемым образом?
Формат ввода
Первая строка входных данных содержит два целых числа n и R — количество жуков и радиус круга соответственно (3 ≤ n ≤ 200, 1 ≤ R ≤ 100).
Каждая из последующих n строк содержит по два целых числа xi и yi — первоначальные координаты очередного жука (0 ≤ |xi|, |yi| ≤ 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
Не могу решить эту задачу, пытался два дня, получаю либо неправильный ответ на 3 тесте, либо превышение по времени исполнения программы, помогите пожалуйста разобраться, что не так(
Как я решал задачу:
Я взял этот вписанный n-угольник и поместил одну из его вершин в точку (0, R) и посчитал координаты остальных вершин. Далее, ответ будет зависеть от угла поворота данного n-угольника относительно его центра, причем угол, на который нужно повернуть можно перебрать, он будет равен от 0 до 2 * pi / n, так как когда мы повернем многоугольник на 2 * pi / n градусов, то у нас просто первая вершина станет на место второй, вторая на место третьей и так далее, то есть в точке (0; R) будет стоять не вершина с номером 1, а вершина с номером n. Допустим у нас есть угол поворота, значит мы можем посчитать координаты n-угольника, повернутого на данный угол через тригонометрические формулы. Как нам оптимально разбить жуков по точкам? Представим жуков и точки как двудольный граф. Сделаем данное разбиение с помощью венгерского алгоритма. Ответ на нашу задачу - время жука, который будет бежать дольше всего. Нам нужно минимизировать это время. Можно представить это как функцию, зависящую от угла поворота, для нее нам нужно найти минимум. Мы можем сделать это с помощью бинарного поиска (бинарный поиск по производной). Вот код:
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-7 ;
const ld pi = acos(-1.0);
ld n;
ld radius;
struct Point {
ld x, y;
};
vector<Point> polygon;
const ll INF = numeric_limits<ll>::max();
ll hungarian(const vector<vector<ll>>& matrix) {
ll height = matrix.size(), width = matrix[0].size();
vector<ll> u(height, 0), v(width, 0);
vector<ll> markIndices(width, -1);
for (ll i = 0; i < height; ++i) {
vector<ll> links(width, -1);
vector<ll> mins(width, INF);
vector<ll> visited(width, 0);
ll markedI = i, markedJ = -1, j;
while (markedI != -1) {
j = -1;
for (ll j1 = 0; j1 < width; ++j1)
if (!visited[j1]) {
if (matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) {
mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
links[j1] = markedJ;
}
if (j == -1 || mins[j1] < mins[j])
j = j1;
}
ll delta = mins[j];
for (ll j1 = 0; j1 < width; ++j1)
if (visited[j1]) {
u[markIndices[j1]] += delta;
v[j1] -= delta;
}
else {
mins[j1] -= delta;
}
u[i] += delta;
visited[j] = 1;
markedJ = j;
markedI = markIndices[j];
}
for (; links[j] != -1; j = links[j])
markIndices[j] = markIndices[links[j]];
markIndices[j] = i;
}
ll result = -INF;
for (ll j = 0; j < width; ++j)
if (markIndices[j] != -1)
result = max(result, matrix[markIndices[j]][j]);
return result;
}
ld dist(Point first, Point scnd) {
return sqrtl((scnd.x - first.x) * (scnd.x - first.x) + (scnd.y - first.y) * (scnd.y - first.y));
}
void build_polygon(ld angle) {
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) };
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> radius;
vector<Point> bugs(n);
for (int i = 0; i < n; i++) {
cin >> bugs[i].x >> bugs[i].y;
}
ld angle = -2 * pi / n;
polygon = { { 0, radius } };
build_polygon(angle);
vector<vector<ll>> matrix1(n, vector<ll>(n)), matrix2(n, vector<ll>(n));
int count = 100;
ld l = angle, r = 0, x;
for (; count--; ) {
x = (l + r) / 2;
for (int i = 0; i < n; i++) {
Point new1 = rotate(polygon[i], x),
new2 = rotate(polygon[i], x + eps);
for (int j = 0; j < n; j++) {
matrix1[i][j] = (long long)(1000000000.0 * dist(new1, bugs[j]));
matrix2[i][j] = (long long)(1000000000.0 * dist(new2, bugs[j]));
}
}
long long f1 = hungarian(matrix1);
long long f2 = hungarian(matrix2);
if (f1 < f2) {
r = x;
}
else {
l = x;
}
}
ld m1 = (l + r) / 2;
for (int i = 0; i < n; i++) {
Point new1 = rotate(polygon[i], m1);
for (int j = 0; j < n; j++) {
matrix1[i][j] = (long long)(1000000000.0 * dist(new1, bugs[j]));
}
}
ld res = hungarian(matrix1) / 1000000000.0;
cout << fixed << setprecision(10) << res;
return 0;
}
P.S. в коде берется угол с знаком минус, потому что я поворачиваю по часовой стрелке, а углы в радианах идут против часовой стрелки