Compute path distance

March 7, 2009 at 1:54 pm 1 comment

This one is interesting too:

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

Advertisements

Entry filed under: Uncategorized.

Computing small factorials Turbo Sort

1 Comment Add your own

  • 1. Narinder Beri  |  March 7, 2009 at 2:01 pm

    After 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: