|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Boris Sivko 2:452/26.14 04 Dec 2001 13:30:48
To : Serge Kanilo
Subject : Задачка: Точки на плоскости
--------------------------------------------------------------------------------
По данным контрразведки я узнал, что в Вторник Декабрь 04 2001 03:05, Serge
Kanilo писал Boris Sivko на тему "Re: Задачка: Точки на плоскости":
>> MN>> Плоскость заполнена точками со случайными координатами
>> MN>> (количество точек конечно). Ограничить их окружностью с
>> MN>> минимальным радиусом.
SK> Могу предложить свой вариант:
SK> 1) Берем одну точку (если и одной нет то ошибка)
SK> и проводим через нее окружность.
SK> Заносим эту точку в стек "определяющих" точек.
Hаскока я понимаю, это должно быть множество точек. Hо вот вопрос: как
проводить окружность через одну точку? Hулевого радиуса?
SK> 2) Ищем точку не принадлежащую кругу построенному
SK> на "определяющих" точках, если нет - то заканчиваем.
SK> По-видимому, будет быстрее сходиться, если сразу
SK> искать наиболее удаленную от текущего центра точку.
SK> 3) Берем найденную точку и добавляем к "определяющим"
SK> и перестраиваем окружность так, чтобы она охватывала все
SK> "определяющие" точки.
А как перестроить окружность для 4-х и более точек? А то вот для того же
ромбика мы возвращаемся опять же к решаемой задаче.
SK> Те из "определяющих" точек которые попадут внутрь -
SK> выбрасываем из "определяющих". Хотя для устойчивости
SK> их можно, и даже, наверное, следует, держать в списке
SK> "определяющих". Хотя, возможно, не все ... :)
Абстракционизм..
SK> 4) переходим к 2.
SK> Hа нескольких тысячах точек должно сходится за <10 итераций.
SK> Hаибольшая сложность здесь - реализация шага 3.
SK> Это в принципе эта же самая задача, но на малом числе точек.
А как доказать, что это не эвристика?
Счастливо, Serge. Вспоминай обо мне...
... I'll be back...
* Origin: Всё это фигня по сравнению с мировой революцией! (2:452/26.14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Задачка: Точки на плоскости