|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 07 Dec 2002 12:36:30
To : Yurij Zabelyshynskij
Subject : Re: Exercise from Cormen
--------------------------------------------------------------------------------
Yurij Zabelyshynskij wrote:
> ...
> Многие подписчики знают книгу Кормена и др. Есть там упражнение
> 35.1-4, цитирую:
>
> "Чтобы узнать, являются ли точки p_i, i от 0 до n-1, вершинами
> выпуклого многоугольника, перечисленными в порядке обхода
> многоугольника, профессор предлагает проверить, что множество углов
> (p_i, p_i+1, p_i+2), i от 0 до n-1, i+1 и i+2 вычисляются по модулю n,
> не содержит одновременно правых и левых поворотов. Покажите, что этот
> способ не всегда дает правильный ответ".
> Рассматриваемые многоугольники являются несамопересекающимися.
>
> Hо я не вижу, в чем неправ профессор. А вы?
В таком условии задачи профессор совершенно прав. При условии рассмотрения
только несамопересекающихся многоугольников, такой способ дает соврешенно
точный ответ на вопрос о выпуклости многоугольника.
--
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
