This problem seems easy , but I have WA on test 8, does anybody know what kind of test is this?

May be greedy wrong?
My solution based on greedy.
Starting from p1=(1,1) we go to nearest(in x+y metric) admissible p2 and so on.
I have wa 9.

Yes!. Greedy is right.
Proof: Let p3 be another admissible point.
We have:
Dist(p1,p2)<=Dist(p1,p3)-Dist(p2,p3);
Dist(p2,n)<=Dist(p3,n)+Dist(p2,p3);
=>
Dist(p1,p2)+Dist(p2,n)<=Dist(p1,p3)+Dist(p3,n)

Edited by author 22.11.2011 14:35