геометрическая задачка, минимальный круг Опции

[Bard]

Всем привет. У меня ту одна задачка по геометрии которую я очень хочу решить. Надеюсь на вашу помощь... Значит так. Задано число N(<=100) и N точек на координатной плоскости. Точки не лежат на координате (0,0) и по модулю не превышают 1000. Нужно найти координаты центра и радиус круга окружность которого соприкасалась бы как мин. с одной точкой и окружала бы все остальные точки.

пример:
6
1 1
1 5
3 6
5 3
9 5
5 9

ответ:
5 4
5

У кого какие идеи?

[Bard]

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

[Lapp]

думаю сначала посторить выпуклую оболочку а потом уже описанную окружность вокруг многоугольника.

Что означает "описанная окружность вокруг многоугольника"? Я не вполне понимаю этот термин. Все равно нужно перебирать треугольники (правда, меньшее количество).

Если минимальность не нужна, то чем плох мой способ (сообщение 4)? Ко всему прочему, он значительно проще и быстрее всяких выпуклых оболочек.

Кстати мой второй способ в смысле минимальности неверен. Позже напишу, почему - сейчас нет времени.

[Lapp]

Вот, немного освободился.
Привожу уже релизованный мой первый (неминимальный) алгоритм:

// нахождение центра окружности
O.x:=(Xmin+Xmax)/2;
O.y:=(Ymin+Ymax)/2;
// нахождение радиуса
R:=0;
for i:=1 to n do with A[i] do begin
  t:=Sqrt(Sqr(x-O.x)+Sqr(y-O.y));
  if t>R then R:=t
end;

Кстати сказать, этот способ допускает простую оценку "неминимальности": радиус окружности меньше, чем Rmin*Sqrt(2) , где Rmin - радиус действительно минимальной окружности. Причем, это грубая оценка (то есть тут именно строгое неравенство). Если нужно, могу сделать поточнее.

Кстати мой второй способ в смысле минимальности неверен.

Сначала процитирую сам себя (неверное решение)

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

Именно "ключевое соображение" тут неверно. Существуют случаи (и нередкие), когда минимальная окружность проходит через две точки, а не через три. Простейший пример - три (или больше) точки на одной прямой. Решение можно изменить так, чтобы оно стало верным. Для этого нужно рассматривать не только окружности, описанные вокруг треугольников, но также и окружности, построенные на каждой паре точек (отрезке) как на диаметре. Это не слишком усложняет алгоритм и гарантирует минимальность