All submissions for this problem are available.
got in to war with Liarland. And the war was becoming dangerous day by day.
To attack the Liarland armies there is a set of co-ordinates that Wonderland army have to follow. To choose which co – ordinate to
visit next there is an algorithm specified by professor WonderMath in Wonderland.
You start at the point with the
least X and greatest Y value, and end at the point with the greatest X.
- You cannot move to a point with a lesser X
value as compared to the X value of the point you are on.
Also for points having the same X value, you need 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,4 and 0,3) we would start with (0,4) .
- You need to visit every point in the plane.
To get an idea about water they have to carry they need to
know the full distance of the attack. Your program must help them to calculate the distance of the full
attack adhering to the above rules.
Imagine you have following points to visit.
Your attacking path according to the above rules will be
0,0 -> 1,10
1,5 -> 1,5
1,10 -> 2,2
So the total distance traveled will be 18.21
You will be given an integer t(1<=t<=20) 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. This is followed by a new line. Then
follow the n points, each being a pair of integers separated by a
single space; followed by a new line. The X and Y coordinates
of each point will be between 0 and 10000 both inclusive.
For each test case, print the total distance traveled by you
from start to finish; keeping in mind the rules mentioned above,
correct to 2 decimal places.
The result for each test case must be on a new line.
- 100 <= N <= 999
- 100 <= N <= 999
3 2 0 0 0 1 3 0 0 1 1 2 2 4 0 0 1 10 1 5 2 2Sample Output:
1.00 2.83 18.21
|Time Limit:||0.18 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.