|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 06 Dec 2002 18:45:01
To : Serge Nozhenko
Subject : Re: Exercise from Cormen
--------------------------------------------------------------------------------
Hi, Serge.
Serge Nozhenko wrote
> Hет там такого условия (что данные точки заведомо
> являются несамопересекающимся многоугольником).
> Вот оригинал: "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.
Hе знаю, как в английском издании, а в переводном в этом месте
написано:
"подробнее о многоугольниках см. в разделе 16.4"
А в разделе 16.4 написано
"Hесамопересекающийся многоугольник (только такие мы и будем, как
правило, рассматривать) называется простым."
Видимо, условие задачи надо понимать так, на вход подается
произвольная последовательность точек, а не обязательно вершины
многоугольника.
> 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
