The Lazy Algorithm
Peeps back at IIITM Gwalior are poster-boys for all the lazybones in the house. They are out seeking ‘jugaad’, or the easiest/shortest way to do a job.
You have a paper and pencil. There are several lines drawn on the paper. Each line is horizontal and no two lines are at same height.
All the lines are arranged from highest to lowest height. You want to sketch a path from a starting point to the last line cutting each of the lines.
You need to calculate the minimum length path that starts from the starting point and ends at the last line. You can draw the lines in any order, you just need to minimize the length.
Note: The start point will be always above the first line
- The first line contains the number of test cases T(1<=T<=400).
- The first line of each testcase contains the number of lines N (1<=N<=1000) .
- The next line contains coordinates of the start point x y.
- Next N lines contains the co-ordinates of the N lines.
- The co-ordinates will be in form y x1 x2, that means that the line is from (x1, y) to (x2, y). x2 will be greater than x1 and y is arranged in descending order. You have to reach the last line. All the co-ordinates are between -7.5* 10^5 to 7.5*10^5.
- For every test case we need to print the minimum distance from the starting point to the finish line. Your answer should contain 6 decimal points.
Input: 2 3 0 5 4 1 3 3 2 4 2 1 3 3 1 4 3 1 6 2 2 5 1 3 6 Output: 3.828427 3.605551
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.