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

[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 12:42

[Lapp]

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

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

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