однократно. Но в
однократно. Но в реальной ситуации может быть задан многоугольник, а затем последовательность точек, про каждую из которых требуется узнать, лежит ли она в многоугольнике. (Возвращаясь к уже упоминавшемуся примеру, представьте себе, что курсор мыши двигается, и нужно все время следить, находится ли он в заданной области.) Тут уже время O(N) может оказаться слишком большим. Оказывается, что его можно уменьшить, если 1 раз потратить усилия на предварительную обработку. Правда, в общем случае это довольно сложная задача, но в некоторых частных случаях она оказывается вполне обозримой для нашего рассказа. Мы обсудим ее позднее.
<<< Предыдущий урок Следующий урок >>>
| Новости | Регистрация | Курсы | Карта сайта | Контактная информация |
Курс 1
Глава Z
Простые геометрические задачи. Задача о принадлежности точки (1)
Задача о принадлежности точки (2)
Задача о принадлежности точки (3). Построение выпуклой оболочки
Начнем с разбора упражнений из предыдущего
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
