минимальная окружность

[undefined]

Имеется облако точек x[i],y[i].Требуется найти минимальную окружность,охватывающую все точки.
NB:Сложность алгоритма не должна зависеть от расположения точек.

[Tails]

1. Найти среднее арифметическое (позицию) точек dx и dy.
2. Найти максимальный радиус среди точек до этих dx, dy.
Два прохода по массиву. Вроде, должно работать.

[ZackMercury]

Tails, неверно :3

[ZackMercury]

Среднее арифметическое точек(оранжевый круг)

Test.swf   (16.7 Кб)

[undefined]

Tails, неверно :3

Да, окружность выходит неминимальная.

[ZackMercury]

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

(если что, если через 5 точек возможно провести окружность, то только одну)

[undefined]

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

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

Алгоритм Tails даст вполне конкретный центр и радиус.Другой вопрос что они неверные будут,кстати, неминимальность хорошо видна если точки раскидать по эллипсу

[undefined]

(если что, если через 5 точек возможно провести окружность, то только одну)

Требование чтоб окружность проходила через все точки не стоит

[ZackMercury]

Ну тогда условие задачи некорректно. "Содержащую точки" буквально означает, что все точки должны принадлежать этой окружности.

[undefined]

Думал и так ясно что невозможно провести окружность через произвольные n точек.
ПС:для однозначного задания окружности достаточно 3 точки,а не 5.
ПС2: поправил условие.