## Compute path distance

*March 7, 2009 at 1:54 pm* *narinderberi* *
1 comment *

This one is interesting too:

http://www.codechef.com/problems/POINTS/

Entry filed under: Uncategorized.

*March 7, 2009 at 1:54 pm* *narinderberi* *
1 comment *

This one is interesting too:

http://www.codechef.com/problems/POINTS/

Entry filed under: Uncategorized.

%d bloggers like this:

1.Narinder Beri | March 7, 2009 at 2:01 pmAfter absorbing the input, sort it as below:

Make a hash where key is x and the value is a vector (min y, max y) which store the min and max y for that x.

So, we now need to move travel each key of the hash.

While traveling, there are 2 distance components that we add up:

1. Jumps from 1 key to another key – Moving from current x to next x. This is simply sqrt(dx*dx + dy*dy).

2. Jumps inside the same key – Moving from max y to min y within the same key. This is simply maxY – minY.

Keep summing up these and you get your answer.