Discussion @ 1058. Chocolate @ Timus Online Judge

Punkrocker Idea for linear solution :) [3] // Problem 1058. Chocolate 26 Feb 2005 18:36

Not very hard to prove, then the breakage-line must create EQUAL ANGLES with sides, connected by it. This idea immediately gives the O(N^3) algorithm. But it could be improved even to O(N). :)

Denis Koshman Re: Idea for linear solution :) // Problem 1058. Chocolate 20 Aug 2008 20:11

Edited by author 20.08.2008 20:22

Erick Wilts Re: Idea for linear solution :) [1] // Problem 1058. Chocolate 23 Jun 2014 21:00

It could be corners instead of sides for the following input.
6
0 0
2 1
4 0
4 4
2 3
0 4

organmusic Re: Idea for linear solution :) // Problem 1058. Chocolate 2 Jul 2016 01:53

to Erick Wilts

CONVEX poligon

Discussion of Problem 1058. Chocolate