задачка

[VBA b0.3]

есть точки на плоскости
нужно найти окружность с минимальным радиусом, такая чтоб все точки были внутри неё.

денег никому не дам просто выложите алгоритм прям сюда всем на обозрение, желательно на сях

все пасиб

а вам слабо ? кулкодеры

[Васо]

Для меня эта задачка чересчур сложная. Поэтому я удалил из условия все буквы, и вот что получилось:

Пысы. Денег можешь не предлагать - мне не в лом...

[Yandex]

>нужно найти окружность с минимальным радиусом, такая чтоб все точки были внутри неё
Это так теперь называется описанная окружность треугольника, образованного тремя твоими точками?

[VBA b0.3]

обращаю внимание самых внимательных на условие задачи, в котором ничего не сказано о количестве точек.

вы просто попробуйте её решить.. задачка всего в две строчки

[Yandex]

Ах, да неусмотрел

>задачка всего в две строчки
Видимо длина у этих строчек достаточно большая Я бы в Кнуте посмотрел, если бы лень было думать.

[Terry]

нужно найти окружность с минимальным радиусом, такая чтоб все точки были внутри неё.

описаная окружность это когда все точки лежат на окружности. Си вспоминать не буду - но алгоритм таков:
ищешь максимальное растояние между двумя точками, делишь его на два.

[Terry]

пипец у вас в воронеже студенты. ничуть думать не хотят. удивительно что мое сообщение - шестое.

[VBA b0.3]

ну опускать публично не буду, думаю сам еще 5 сек подумаешь и поймешь что эта окружность не факт что будет содержать ВСЕ точки внутри себя она будет лишь проходить чере две точки максимально удалённые друг от друга и все...

низачет!

ps в воронеже програмисты то_что_нада

[Terry]

ок. поняла. тогда - ищем максимально удаленые друг от друга точки (A и B). Точка С - середина отрезка AB. Ищем точку D, максимально удаленую от С. Если СD больше AC, тогда искомая окружность описана вокруг треугольника ABD, если наоборот - центр окружности в точке С, радиус - АС

[VBA b0.3]

для тех кто не понял где облажались могу картинку - раскраску нарисовать

Terry - умничка

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

[Terry]

радиус будет минимален потому что
второе условие - радиус AC - все понятно
если точки А и В максимально удалены друг от друга - окружность будет проходить именно через эти точки. Осталось найти третью. третья точка должна быть максимально удалена от отрезка AB ( одновременно и от А и от В) - чтобы не путаться и не путать алгоритм - вводим точку с
где подвох?

[Terry]

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

[VBA b0.3]

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

но уже явно зачет

[Terry]

давайте думать еще. если СD > CA, значит D находится в области, образованной пересечением двумя окружностями AB и BA (первая буква - центр, вторая точка на окружности) и ислючением из получившейся области окружности CA. То есть у нас частный случай. требуемая окружность описана около A, B и D.
Если мы найдем точку D' (D'C > AC), то D' обязательно лежит по одну сторону с D От АВ. В противном случае DD' > AВ, а мы выбирали самый большой отрезок. Все варианты мы рассмотрели.

[Yandex]

Возьмем три точки A,B и D. A и B наиболее удалены от друг друга - ок. - С - середина отрезка AB - ок. Пусть D лежит внутри окружности - радиус найден - да?
Вывод: центр описываемой окружности всегда лежит на середине стороны треугольника! Сенсация!
Или я опять где то не досмотрел (тогда сорри с работы убегаю уже)

[Terry]

мы уже говорили о этом. точка D может лежать вне окружности CA.

[Yandex]

А все кажется понял - ответ: искомая окружность проходит через две макс. удаленные точки множества A и B и третью точку, которая макс. удалена от центра отрезка AB. Просто это было так описано, что ужас какой то, особенно смутило:
Post#9
>Если СD больше AC,..., если наоборот - центр окружности в точке С, радиус - АС
[мой бред]

Post#11
>должна быть максимально удалена от отрезка AB ( одновременно и от А и от В)
Супер формулировка выражающая AD+BD=max

А что правда, эта окружность должна проходить через две макс. удаленные точки?

>пипец, бабы думают о задачке для мужиков по информатике
Где ж тут информатика? Школьная геометрия

[Dr.PC]

А все кажется понял - ответ: искомая окружность проходит через две макс. удаленные точки множества A и B и третью точку, которая макс. удалена от центра отрезка AB.

Да нифига подобного!

[Terry]

А все кажется понял - ответ: искомая окружность проходит через две макс. удаленные точки множества A и B и третью точку, которая макс. удалена от центра отрезка AB.

не всегда.

[Yandex]

Эх, меня клинит капитально, пойду яду выпью

[The_God]

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

[Terry]

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

[VBA b0.3]

ну и ....

[maximn]

чем я хуже, тоже напишу сюда..
покоординатно середины имхо,а макс расст будет радиусом..
примерно так

добавил
только x=(x2+x1)/2, y=(y2+y1)/2

[VBA b0.3]

низачет

[Terry]

читаем 11 и 14 пост и смотрим картинку.

[Terry]

на картинке АВ = АD = DB
maximn на картинке случай, когда твой алгоритм не подходит

[maximn]

Сообщение от VBA b0.3

низачет

рисуй контрпример

[maximn]

.....

[Terry]

зеленая окружность нарисована по способу maximn
сиреневая по моему способу.
невооруженным глазом видно, моя меньше.