Вычисление оптимальной точки пересечения окружностей

[Ony]

Собственно есть задача по вычислению оптимальной точки, которая находится в области пересечения большинства окружностей, т.е. попадает внутрь большинства окружностей.

Исходные данные:
- Список точек центра окружностей
- Дистанция = радиус от центра окружности.


Необходимо вычислить точку (и саму область) в области, полученной из точек пересечения окружностей (если окружности пересекаются), которая бы включала в себя области большинства из окружностей (размер области не важен). Т.е. областей пересечения может быть несколько, в этом случает нам подойдет та, которая включает в себя части большинства окружностей.

Может ли кто-нибудь с этим помочь ? :) Большое спасибо!

[ИСН]

Окружностей Кругов.
По сути, пахнет перебором размера $2^n$; кое-что лишнее можно отсечь, но если большинство кругов действительно пересекаются все вместе, то - - -

-- менее минуты назад --

А хотя нет, можно проще.
1. Для каждого круга находим список тех, которые с ним пересекаются. (Тут придётся посчитать все попарные расстояния - квадратичный труд.)
2. Берём один круг (любой; лучше начинать с тех, у которых пересекающих больше) и выписываем углы пересечений. Типа "перерезан кругом номер 21 между 65 и 135 градусами, кругом 54 с... по...".

-- менее минуты назад --

3. Сортируем этот список углов, проходим по нему и находим, где пересечений больше всего.
4. То же самое для остальных кругов.
5. ...
6. PROFIT!

[Ony]

а можно ли это как-то обличить в формулу ? :)

[ИСН]

Если возник такой вопрос, то Вы уже зашли не туда.
В каком-то смысле можно, но этого не надо делать.

-- менее минуты назад --

Ну, будет там что-то типа $\max\limits_{i=1..n}\;\; \max\limits_{0\leqslant\varphi<2\pi}\;\sum\limits_j{1\over 2}\Big(sgn(\varphi-\varphi_1)+sgn(\varphi_2-\varphi)\Big)$ - а толку-то?
(На место $\varphi_1$ и $\varphi_2$ надо подставить границы диапазона углов круга $i$, отрезанного кругом $j$. Тоже несложно, но арксинусы, грязь, мухи, вот это всё.)