Re: Exercise from Cormen

From

Yurij Zabelyshynskij ()

To

Serge Nozhenko

Date

2002-12-06T17:45:01Z

Area

RU.ALGORITHMS

From: "Yurij Zabelyshynskij" <ergo@sky.net.ua>

Hi, Serge.
Serge Nozhenko wrote
>   Нет там такого условия (что данные точки заведомо
> являются несамопересекающимся многоугольником).
> Вот оригинал: "Professor Amundsen proposes the following
> method to determine whether a sequence (p0, p1, . . . , pn-1)
> of n points forms the consecutive vertices of a convex polygon.

Не знаю, как в английском издании, а в переводном в этом месте
написано:
"подробнее о многоугольниках см. в разделе 16.4"

А в разделе 16.4 написано
"Несамопересекающийся многоугольник (только такие мы и будем, как
правило, рассматривать) называется простым."

Видимо, условие задачи надо понимать так, на вход подается
произвольная последовательность точек, а не обязательно вершины
многоугольника.

> Output "yes" if the set {angle(pi, pi+1, pi+2): i = 0, 1, . . . .,
> n - 1}, where subscript addition is performed modulo n, does not
> contain both left turns and right turns; otherwise output "no".

>   Так что в качестве контрпримера подходит даже ((1,1), (2,2),
> (3,3)) :)

Почему же? Здесь нет ни левых, ни правых поворотов, так что алгоритм
скажет "да", и это будет правильно - он действительно выпуклый. :)

--
WBR, Yura.


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)