Exercise from Cormen

From

Anton Kuznetsov (2:5030/566.13)

To

Yurij Zabelyshynskij

Date

2002-12-05T23:18Z

Area

RU.ALGORITHMS

                Всех тебе благ, Yurij!

 YZ> "Чтобы узнать, являются ли точки p_i, i от 0 до n-1, вершинами
 YZ> выпуклого многоугольника, перечисленными в порядке обхода
 YZ> многоугольника, профессор предлагает проверить, что множество углов
 YZ> (p_i, p_i+1, p_i+2), i от 0 до n-1, i+1 и i+2 вычисляются по модулю n,
 YZ> не содержит одновременно правых и левых поворотов. Покажите, что этот
 YZ> способ не всегда дает правильный ответ".
 YZ> Рассматриваемые многоугольники являются несамопересекающимися.
 YZ>
 YZ> Но я не вижу, в чем неправ профессор. А вы?

 Ну, например возьми правильную 5-тиконечную звезду... Вершину у нее - вершины
звезды... (Пересечения ребер - не вершины)... Там все треугольники
ориентированы одинаково, а 5-ти угольник не выпуклый...

 Вот так...

                            До свидания, Yurij!
 * Origin: ФТШ - школа наша! (2:5030/566.13)