Discussion @ 1058. Chocolate @ Timus Online Judge

Idea for linear solution :)

Posted by Punkrocker 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). :)

Re: Idea for linear solution :)

Posted by Denis Koshman 20 Aug 2008 20:11

Edited by author 20.08.2008 20:22

Re: Idea for linear solution :)

Posted by Erick Wilts 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

Re: Idea for linear solution :)

Posted by organmusic 2 Jul 2016 01:53

to Erick Wilts

CONVEX poligon

Discussion of Problem 1058. Chocolate