Версия для печати темы

Автор: Bard 30.12.2008 19:09

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

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

ответ:
5 4
5

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

Автор: xds 30.12.2008 22:32

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

Автор: Lapp 31.12.2008 9:13

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

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

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

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

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

Автор: Lapp 31.12.2008 12:48

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

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

Автор: Гость 1.01.2009 6:31

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

Автор: Lapp 1.01.2009 9:47

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

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

Автор: Bard 3.01.2009 1:55

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

Автор: Bard 3.01.2009 2:45

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

Автор: Lapp 3.01.2009 5:38

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

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

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

Автор: Lapp 3.01.2009 8:01

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

// нахождение центра окружности
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 5.01.2009 0:33

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

Автор: Lapp 5.01.2009 12:46

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