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

Нужна наименьшая окружность, содержащая все точки набора. Она определяется двумя или тремя точками набора - и это ключ ко всему алгоритму.

Почему двумя или тремя

Пусть окружность минимальна. Если на ней лежит меньше двух точек, её можно сжать; если ровно две и они не диаметрально противоположны - сдвинуть центр к середине и сжать. Значит либо две точки образуют диаметр, либо три лежат на окружности.

Алгоритм

Перебираем точки по очереди. Если очередная уже внутри текущей окружности - ничего не делаем. Если нет - она обязана лежать на границе новой минимальной окружности, и задача сводится к той же для префикса, но с одной закреплённой точкой. Дальше то же самое ещё раз.

shuffle(p);                                  // случайный порядок обязателен
Circle c = {p[0], 0};
for (int i = 1; i < n; i++) {
    if (inside(c, p[i])) continue;
    c = {p[i], 0};
    for (int j = 0; j < i; j++) {
        if (inside(c, p[j])) continue;
        c = from2(p[i], p[j]);
        for (int k = 0; k < j; k++)
            if (!inside(c, p[k])) c = from3(p[i], p[j], p[k]);
    }
}

Три цикла и линейное время

Выглядит как $O(n^3)$, но при случайном порядке точек математическое ожидание времени - $O(n)$. Причина: вероятность того, что $i$-я точка окажется вне окружности, построенной по первым $i-1$, равна примерно $3/i$ - ведь окружность определяется тремя точками из $i$. Сумма $\sum 3/i \cdot i = 3n$.

Перемешивание - не украшение, а условие корректности оценки. Без него на упорядоченном входе алгоритм честно даст кубическое время.

Проверка

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

Точность

Центр и радиус вещественные, поэтому проверка «точка внутри» делается с эпсилоном. Сравнивать лучше квадраты расстояний и с относительным допуском - при координатах $10^9$ абсолютный эпсилон в $10^{-9}$ бессмыслен.

Смежное

• Окружности;
• Выпуклая оболочка - минимальная окружность опирается только на её вершины.