Exercise from Cormen

From

Serge Nozhenko (2:5020/175.1)

To

Borodin Anatoly

Date

2002-12-06T03:50:32Z

Area

RU.ALGORITHMS

06 Dec 02 01:01, Borodin Anatoly wrote to Borodin Anatoly:

 BA> Pardon!!! При внимательном изучении условия видно, что фигура не
 BA> пересекает саму себя :((( И пятиконечная звезда тоже не проходит

  Нет там такого условия (что данные точки заведомо являются несамопересекающимся многоугольником). Вот оригинал: "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)