Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
задачка |
Философия, технологии, алгоритмы! |
|
|
Опции темы |
06.12.2005, 14:59 | #31 |
мегапиксель
|
а я б вообще перебором всех точек делала: взяла бы пару точек и диаметром=расстоянию между ними начертила окружность. потом бы взяла следующую точку, если принадлежит окружности, то готу ве некст точка, если не принадлежит, то увеличила бы окружность до этой точки. и так до тех пор, пока все точки не окажутся вовнутрях на етом круге. далее, вычислила б его диаметр.
ЗЫ: си не знаю ЗЫЗЫ: и рисовать я не умею |
06.12.2005, 15:02 | #32 | |
girl-1.0asp
Сообщений: 566
Регистрация: 20.09.2005
Возраст: 41
Не в сети |
Цитата:
|
|
06.12.2005, 15:15 | #33 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
наверное стоит сделать вывод что такими геометрическими вычислениями эта задача не решается... или все таки решается ?
я сам-то её решил "перебором",т.е. сначала экспеременетально убедился что такая окружность - единственная, а потом нахожу её способом похожим на "деление пополам". плюс - задача решается минус - медленно, всмысле если найти геометрическое решение её, любое, то оно будет заведомо быстрее чем моё |
06.12.2005, 15:30 | #34 |
мегапиксель
|
ааа. эта задача старая уже оказывается http://www.inf.ethz.ch/personal/gaertner/miniball.html
|
06.12.2005, 15:36 | #36 | |
error #65535
Сообщений: 5,240
Регистрация: 16.11.2003
Возраст: 24
Не в сети |
Цитата:
|
|
06.12.2005, 15:50 | #38 | |
error #65535
Сообщений: 5,240
Регистрация: 16.11.2003
Возраст: 24
Не в сети |
Цитата:
я же не просто так сижу, я на работе - ваяю (нетленку как обычно).. =) и вообще, вы меня тут не видели если что.. |
|
06.12.2005, 17:00 | #39 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
скачаю, посмотрю, но я думаю что и там не минимальный радиус это условие наверняка заменят на чтото типа "а давай те ка найдем не минимальный радиус, а тот который быстро ищется" таких алгоритмов я кучу видел.. они не являются решением поставленой задачи
|
06.12.2005, 21:31 | #41 |
Форумец
Сообщений: 142
Регистрация: 17.12.2002
Возраст: 43
Не в сети |
Такой вариант:
Перебираем все точки, находя 2 наиболее удалённые (А и Б). Расчитываем половину расстояния (назовём R1). Расчитываем координаты середины отрезка. Перебираем все точки относительно расчитанного центра отрезка, и ищем максимально удалённую (C). Если расстояние от максимально удалённой точки равно R1, то центр отрезка является центром окружности, а R1 её радиусом, иначе на окружности будут лежать 3 точки,и рассчитаем окружность по этим 3-м точкам (А,Б,С): {известно 2 отрезка АC и СБ. От каждого отрезка из центра проводим перпендикуляр. Пересечение перпендикуляров есть центр искомой окружности. Далее легко рассчитать её радиус.} Здесь рисовать влом, но получаецца прально В случае успеха не откажусь от 300 зелёных |
07.12.2005, 11:17 | #44 |
Форумец
Сообщений: 166
Регистрация: 02.08.2005
Возраст: 44
Не в сети |
доказательство минимальности должно быть в решении
можно дома запрограмить этот алгоритм и сравнить его результат с правльным, но медленным алгоритмом... но этож делать надо просто еще смущает что слишком он простой |