Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
задачка |
Философия, технологии, алгоритмы! |
|
|
Опции темы |
02.12.2005, 11:16 | #1 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
задачка
есть точки на плоскости
нужно найти окружность с минимальным радиусом, такая чтоб все точки были внутри неё. денег никому не дам просто выложите алгоритм прям сюда всем на обозрение, желательно на сях все пасиб а вам слабо ? кулкодеры |
02.12.2005, 15:43 | #6 | |
girl-1.0asp
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41
Не в сети |
Цитата:
ищешь максимальное растояние между двумя точками, делишь его на два. |
|
02.12.2005, 15:50 | #8 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
ну опускать публично не буду, думаю сам еще 5 сек подумаешь и поймешь что эта окружность не факт что будет содержать ВСЕ точки внутри себя она будет лишь проходить чере две точки максимально удалённые друг от друга и все...
низачет! ps в воронеже програмисты то_что_нада |
02.12.2005, 15:59 | #9 |
girl-1.0asp
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41
Не в сети |
ок. поняла. тогда - ищем максимально удаленые друг от друга точки (A и B). Точка С - середина отрезка AB. Ищем точку D, максимально удаленую от С. Если СD больше AC, тогда искомая окружность описана вокруг треугольника ABD, если наоборот - центр окружности в точке С, радиус - АС
|
02.12.2005, 16:05 | #10 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
для тех кто не понял где облажались могу картинку - раскраску нарисовать
Terry - умничка только еще нужно доказать что эта окружность будет с минимальным радиусом а в этом я сомневаюсь сильно при таком алгооритме... |
02.12.2005, 16:14 | #11 |
girl-1.0asp
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41
Не в сети |
радиус будет минимален потому что
второе условие - радиус AC - все понятно если точки А и В максимально удалены друг от друга - окружность будет проходить именно через эти точки. Осталось найти третью. третья точка должна быть максимально удалена от отрезка AB ( одновременно и от А и от В) - чтобы не путаться и не путать алгоритм - вводим точку с где подвох? |
02.12.2005, 16:27 | #14 |
girl-1.0asp
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41
Не в сети |
давайте думать еще. если СD > CA, значит D находится в области, образованной пересечением двумя окружностями AB и BA (первая буква - центр, вторая точка на окружности) и ислючением из получившейся области окружности CA. То есть у нас частный случай. требуемая окружность описана около A, B и D.
Если мы найдем точку D' (D'C > AC), то D' обязательно лежит по одну сторону с D От АВ. В противном случае DD' > AВ, а мы выбирали самый большой отрезок. Все варианты мы рассмотрели. |
02.12.2005, 17:17 | #15 |
Кэп Улитка
Сообщений: 8,067
Регистрация: 04.05.2005
Возраст: 43
Не в сети |
Возьмем три точки A,B и D. A и B наиболее удалены от друг друга - ок. - С - середина отрезка AB - ок. Пусть D лежит внутри окружности - радиус найден - да?
Вывод: центр описываемой окружности всегда лежит на середине стороны треугольника! Сенсация! Или я опять где то не досмотрел (тогда сорри с работы убегаю уже) |
02.12.2005, 20:40 | #17 |
Кэп Улитка
Сообщений: 8,067
Регистрация: 04.05.2005
Возраст: 43
Не в сети |
А все кажется понял - ответ: искомая окружность проходит через две макс. удаленные точки множества A и B и третью точку, которая макс. удалена от центра отрезка AB. Просто это было так описано, что ужас какой то, особенно смутило:
Post#9 >Если СD больше AC,..., если наоборот - центр окружности в точке С, радиус - АС [мой бред] Post#11 >должна быть максимально удалена от отрезка AB ( одновременно и от А и от В) Супер формулировка выражающая AD+BD=max А что правда, эта окружность должна проходить через две макс. удаленные точки? >пипец, бабы думают о задачке для мужиков по информатике Где ж тут информатика? Школьная геометрия |