|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Boris Sivko 2:452/26.14 03 Dec 2001 21:57:39
To : Nickita A Startcev
Subject : Задачка: Точки на плоскости
--------------------------------------------------------------------------------
Отвечать на письмо на тему "Задачка: Точки на плоскости" очень просто. Когда
часы пробили ровно 18:39, а календарь показывал Воскресенье Декабрь 02 2001, это
сделал Nickita A Startcev. А теперь и моя очередь:
MN>> Плоскость заполнена точками со случайными координатами
MN>> (количество точек конечно). Ограничить их окружностью с
MN>> минимальным радиусом.
MN>> Каковы будут идеи?
NS> Введем функцию R(x,y) где x,y координаты центра, R максимальное
NS> расстояние точек от (x,y). Смотрим значение и градиент этой функции в
NS> крайних точках. Функция кусочно-линейна(?), можно смело спуститься по
NS> градиенту.
Ты представляешь, что это за функция будет при 100 точках? И скока времени она
будет вычислятся?
Идея 1(мини-ускоритель): ограничиваем все точки многоугольником(выпуклым) и
работаем только с точками, которые являются вершинами многоугольника.
Идея 2(решение):
Основывается на утверждении, что решение является окружностью, описанной
вокруг трёх точек(как минимум). Действительно, если опишем окружность через 2 и
менее точки, то мы можем смело как-то уменьшить ответный радиус, т.к. для этих
двух все остальные находятся внутри данной.
Остаётся перебрать все тройки точек многоугольника.
Hе забудьте крайние случаи - 1 и 2 точки.
Счастливо, Nickita. Вспоминай обо мне...
... I'll be back...
* Origin: Я такой же осёл, как и Вы, сэр! (2:452/26.14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Задачка: Точки на плоскости