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

[Bard]

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

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

ответ:
5 4
5

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

[xds]

1) перебором построить выпуклый многоугольник, с вершинами в точках из заданного множества, такой, что все точки множества лежат внутри него (включая стороны); эксплуатируется уравнение прямой;
2) отрезок максимальной длины, построенный на вершинах многоугольника - диаметр искомой окружности.

[Lapp]

1) перебором построить выпуклый многоугольник, с вершинами в точках из заданного множества, такой, что все точки множества лежат внутри него (включая стороны); эксплуатируется уравнение прямой;
2) отрезок максимальной длины, построенный на вершинах многоугольника - диаметр искомой окружности.

Боюсь, так не выйдет.. Контрпример - три точки в вершинах равностороннего треугольника.

Условие несколько хитрое.. В нем ничего не говорится про минимальность окружности. Если минимальность не нужна, то все просто. Например, можно найти Xmin, Xmax, Ymin и Ymax. Тогда прямоугольник с этими координатами будет вмещать все множество. Построим описанную окружность, а затем [далее неверно, см. ниже] сместим ее так, чтобы она проходила через, например, крайнюю точку по Х. Если таких точек несколько - то через две, имеющие минимальную и максимальную координату Y. [далее снова верно]

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

Bard, уточни про минимальность, плз.

PS
Тебе правда нужна такая программа на Паскале как итог этой темы, или мне перенести тему в Алгоритмы?

Сообщение отредактировано: Lapp - 31.12.2008 8:42

[Lapp]

Вот это мое рассуждение в предыдущем мессадже неправильное:

сместим ее так, чтобы она проходила через, например, крайнюю точку по Х. Если таких точек несколько - то через две, имеющие минимальную и максимальную координату Y.

Верно будет так:
У нас есть окружность, описанная вокруг максимального вмещающего прямоугольника (Xmin, Xmax, Ymin и Ymax). Подсчитаем расстояние от центра этой окружности ( (Xmin+Xmax)/2, (Ymin+Ymax)/2 ) до всех точек. Искомая окружность имеет центр в той же точке, а ее радиус равен максимуму из всех найденных расстояний.

[Гость]

А можо-ли попробовать так:найти точку,которая по координатам будет ближе к 0,0 и найти точку,которая ближе будет к 1000,1000?Расстояние между ними-радиус окружности,одна из них-её центр(окружности)...или я ошибаюсь?

[Lapp]

найти точку,которая по координатам будет ближе к 0,0 и найти точку,которая ближе будет к 1000,1000?Расстояние между ними-радиус окружности,одна из них-её центр(окружности)

Несколько странно.. Почему именно (1000,1000), а не (-1000,-1000) или (1000,-1000)? И потом - самая близкая к (1000,1000) - это не обязательно самая далекая от (0,0). Например, точка (900,900) ближе к (1000,1000), чем (800,1000), но она ближе к (0,0), чем (800,1000).

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

[Bard]

Всем привет. Извиняюсь за поздний отклик. Новогоднее настроение только утихает. Ну во первых пост гостя это не мой пост. во вторых метод который предложил xds не катит. а в третих слово минимальность не упомянута в условии задачи. просто окружность должна соприкасаться как мин. с одной точкой и окружать все остальные... ну я подумал что это и есть минимальный круг. ведь меньше не куда...

[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 - радиус действительно минимальной окружности. Причем, это грубая оценка (то есть тут именно строгое неравенство). Если нужно, могу сделать поточнее.

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

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

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

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

[Bard]

Все сделал!!! Огромное спс Лапп... Твой алго очень мне помог. Вот только не нужен никакой прямоугольник. Можно просто взять мин/макс точек. Еще раз спс Лапп

[Lapp]

только не нужен никакой прямоугольник. Можно просто взять мин/макс точек

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