У меня следующая геометрическая проблема: Вам дан круг с центром в начале координат - C (0, 0) и радиусом 1. Внутри круга даны N точек, которые представляют центры N различных кругов. Вас просят найти минимальный радиус маленьких кругов (радиусы всех кругов равны), чтобы покрыть всю границу большого круга.
Число кругов: 3 ≤ N ≤ 10000, а задача должна быть решена с точностью до P десятичных знаков, где 1 ≤ P ≤ 6.
Например:
N = 3 и P = 4
и координаты:
(0,193, 0,722)
(-0,158, -0,438)
(-0,068, 0,00)
Радиус маленьких кружков: 1,0686.
У меня есть следующая идея, но моя проблема заключается в ее реализации. Идея состоит в бинарном поиске, чтобы найти радиус, и для каждого значения, полученного бинарным поиском, чтобы попытаться найти все точки пересечения между маленькими кружками и большим. В результате у каждого пересечения будет дуга. Следующий шаг - «спроецировать» координаты дуг на оси X и Y, в результате чего получается количество интервалов. Если воссоединение интервалов от оси X и оси Y в результате дает интервал [-1, 1] на каждой оси, это означает, что весь круг покрыт.
Чтобы избежать проблем с точностью, я подумал о поиске между 0 и 2 × 10 P , а также принятии радиуса равным 10 P , таким образом исключив цифры после запятой, но моя проблема состоит в том, чтобы выяснить, как имитировать пересечение кругов, а затем узнать, образует ли воссоединение полученных интервалов интервал [-1, 1].
Любые предложения приветствуются!