For it is a convex polygon the best path won't self-cross, so a vertex Pi can only be connected to Pi-1 or Pi+1.

Good Luck!

Edited by author 11.08.2006 16:27

Sorry, what I meant was Pi must be connected to Pi-1 or Pi+1 or both of them.

Then why do you call it DP and O(N^2)? It'll be just O(N) - find shortest side and send the loop around ploygon excluding that side.

Edited by author 12.08.2008 16:38

I think it's true only when we have already fixed one edge and are trying to create path by building a part of one's before the fixed edge and another part after it. There is only 2 ways to create a path when one edge is fixed (read http://acm.timus.ru/forum/thread.aspx?space=1&num=1143&id=14857&upd=633229528200233510)

And also when edge[i][j] is fixed, we can build this 2 pathes unambiguously using greedy thoughts