минимальная охватывающая окружность

[s-andriano]

Сообщение от BDA

Просто до такого умозаключения сложно добраться из Вашего первого поста

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

[BDA]

Сообщение от s-andriano

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

Ну да
Но, похоже, истина нужна только седовласым старожилам, а ТС уже небось сдала программу

[s-andriano]

Сообщение от Abstraction

Итеративный способ: описать окружность вокруг первых трёх точек, затем последовательно проверять очередные точки на "лезет-не лезет" и в случае необходимости перестраивать окружность перебором всех троек точек. Долго выполняется, зато легко программируется.

Сложность O(n^4). Многовато.

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

Могу, кстати, предложить метод уменьшения перебора.
Легко видеть, что окружность не может быть меньше вписанной в ограничивающий прямоугольник и больше описанной вокруг него.
Отсюда следует, что возможные центры лежат в пределах круга, радиус которого вычисляется из радиусов вписанной и описанной окружности.
Все окружности, центры которых лежат вне указанного круга, отбрасываем без проверки точек.