Idea for linear solution :)

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 :)

*Edited by author 20.08.2008 20:22*

Re: Idea for linear solution :)

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 :)

to Erick Wilts

CONVEX poligon