MATOPE - Mario meets princess Peach
There is a set of points in the 2D plane. Mario starts at the point with the least X and greatest Y value, and ends at the point with the greatest X and least Y value where princess Peach is waiting for him. The rules for the movement are:
- Mario can not move to a point with a lower X value as compared to the X value of the point he is on.
- For points having the same X value, Mario needs to visit the point with the greatest Y value before visiting the next point with the same X value. So, if there are 2 points: (0, 2 and 2, 0) Mario would start with (0, 2) - i.e. least X takes precedence over greatest Y.
- Mario needs to visit every point in the set.
Now, Princess Peach wants you to write a code to find the distance Mario has to travel to meet her.
Input
First line of the input would have an integer t (1 <= t <= 3) representing the number of test cases. A new line follows; after which the t test cases are given. Each test case starts with a blank line followed by an integer n (2 <= n <= 100000), which represents the number of points to follow. Following n lines would have a pair of integers (X and Y coordinates (0 <= X, Y <= 10000)) separated by a single space.
Output
For each test case, print the total distance Mario has to travel from start to finish; keeping in mind the rules mentioned above, correct to 2 decimal places.
Example
Input: 3 2 0 0 0 1 3 0 0 3 3 2 2 4 0 0 1 15 1 7 2 1 Output: 1.00 4.24 29.12
hide comments
Francky:
2013-04-05 07:26:04
Moved to tutorial.
|
|
Mitch Schwartz:
2013-04-05 02:49:57
Trivial task, should be moved to tutorial. |
|
Eduardo Nunes:
2013-04-04 17:23:50
good luck, mario... :-) |
Added by: | Devanshi |
Date: | 2013-04-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |