Даны n (n ‹= 1000) окружностей ((x;y), r), где (x;y) = координаты центра окружности, r = радиус. х, у, г ‹ = 10 ^ 6. x, y, r могут быть действительными числами.
Задача состоит в том, чтобы найти точку (x; y), покрытую всеми окружностями, или определить, что таких точек нет. Координаты точки тоже могут быть действительными числами.
Нет идей, как это сделать, может кто-нибудь помочь, пожалуйста?
(x, y)? 27.12.2020 Предполагая, что под кругом вы подразумеваете то, что математики назвали бы закрытым диском, существует алгоритм времени O (n²) с простыми структурами данных.
Для k от 1 до n алгоритм находит точку пересечения первых k дисков, предполагая, что такая точка существует. Начните с центра первого диска. Для каждого диска после первого проверьте, принадлежит ли текущая точка этому диску. Если так, отлично. Если нет, то либо пересечение пусто, либо пересечение содержит точку на границе текущего диска (отрезок прямой от текущей точки до любой точки пересечения всех дисков должен пересекать границу). В этом случае найдите новую точку, пересекая границу (окружность) с каждым из предыдущих дисков, что является более простой задачей 1D.
Ожидается, что это может пойти еще быстрее, если мы рандомизируем порядок дисков, но я не разработал доказательство. Будем надеяться, что при n ≤ 1000 O(n²) достаточно быстро.
Шарир (Задачи пересечения и ближайших пар для набора плоских дисков, 1985), возможно, дал алгоритм O (n log² n) за время, но я не могу сказать это из аннотации.
