|
Ответ: Геометрическая задачка
Все таки я нашел точное решение, которое работает за O(n^4) что достаточно много
Короче по теореме хелли и следующей из нее теореме юнга можно перебрать все двойки тройки и четверки точек и найти центр наименьшего шара, включающих их. После выбрать центр наименьшего из полученных шаров. Но такое решение в систему по времени не проходит, проходит только приближенное
там по условие может быть погрешность не больше 10-6
ну а численных решений неколько, самое быстрое это три вложенных тернарных поиска по координатам (хотя многие делали и одним)
|