|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 06 Dec 2002 04:50:32
To : Borodin Anatoly
Subject : Exercise from Cormen
--------------------------------------------------------------------------------
BA> Pardon!!! При внимательном изучении условия видно, что фигура не
BA> пересекает саму себя :((( И пятиконечная звезда тоже не проходит
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. 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". Show that although this method runs in
linear time, it does not always produce the correct answer. Modify the
professor'r method so that it always produces the correct answer in linear
time."
Так что в качестве контрпримера подходит даже ((1,1), (2,2), (3,3)) :)
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
