{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan style\u003d\"color: black;\"\u003eDuring their honeymoon, Mrs and Mr Smith went to the Himalayas. How they were surprised when they observed that, during the sunset, all the snow touched by the sunbeams turned red.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tSuch a magnificent landscape leaves everyone plenty of emotion, but Mr Smith\u0026#39;s number obsession overcame all this. He rapidly began evaluating distances, which made Mrs Smith quite upset.\u003c/p\u003e\r\n\u003ch2\u003e\r\n\t\u003cspan style\u003d\"color: rgb(0, 96, 0);\"\u003eProblem\u003c/span\u003e\u003c/h2\u003e\r\n\u003cp\u003e\r\n\tYour work is to help him calculate the size, in meters, of the mountainsides that became red as the sun sets. Mr Smith\u0026#39;s honeymoon depends on you! Please be quick and efficient.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor the sake of simplicity, consider that, during the sunset, the sunbeams are horizontal and assume that the landscape is described by the set of coordinates of the mountain peaks and cols. This can be depicted by the following figure. A landscape, in this context, is then a sequence of peaks and cols (i.e., only a col follows a peak and conversely).\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u003cimg height\u003d\"506\" src\u003d\"http://uva.onlinejudge.org/external/9/p920.png\" width\u003d\"947\" /\u003e\u003c/p\u003e\r\n\u003cp\u003e\r\n\tNote that, in this picture, the sunny mountainsides are emphasized by bold lines and the coordinates of the landscape are emphasized by bold points.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThus, the goal of this problem is to calculate the total length in meters of the bold lines.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tFor this task consider that: (1) for all coordinates (\u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e), 0\u003cspan style\u003d\"font-family: Symbol;\"\u003e \u0026lt;\u003d\u003c/span\u003e \u003ci\u003ex\u003c/i\u003e\u003cspan style\u003d\"font-family: Symbol;\"\u003e \u0026lt;\u003d\u003c/span\u003e 30000 and 0 \u0026lt;\u003d \u003ci\u003ey \u003c/i\u003e\u0026lt;\u003d 8848; (2) the unit is the \u003cem\u003emeter\u003c/em\u003e; (3) all the X-coordinates are pair-wise distinct; (4) the leftmost point has 0 as X-coordinate and the rightmost point has 0 as Y-coordinate; (5) The total number of coordinates given is \u003ci\u003en\u003c/i\u003e\u003cspan style\u003d\"font-family: Symbol;\"\u003e \u0026lt;\u003d \u003c/span\u003e100.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp align\u003d\"left\"\u003e\r\n\tThe first line of input contains \u003ci\u003eC\u003c/i\u003e (\u003ci\u003e0 \u0026lt; C \u0026lt; 100\u003c/i\u003e ), the number of test cases that follows.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tEach test case starts with a line containing the number \u003ci\u003eN\u003c/i\u003e of coordinate pairs. The remaining\u0026nbsp; \u003ci\u003eN\u003c/i\u003e lines for each test case contain the coordinates defining the landscape. Each of these lines contains two integers, \u003ci\u003ex\u003c/i\u003e and \u003ci\u003ey\u003c/i\u003e, separated by a single space. The first integer, \u003ci\u003ex\u003c/i\u003e, is the X-coordinate, and the second, \u003ci\u003ey\u003c/i\u003e, is the Y-coordinate of the considered point.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tThe output is formed by a sequence of lines, one for each test case.\u0026nbsp;Each line contains a single real number with exactly two decimal digits. This number represents the length in meters of the sunny mountainsides for the corresponding test case.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t2\u003cbr /\u003e\r\n\t11\u003cbr /\u003e\r\n\t1100 1200\u003cbr /\u003e\r\n\t0 500\u003cbr /\u003e\r\n\t1400 100\u003cbr /\u003e\r\n\t600 600\u003cbr /\u003e\r\n\t2800 0\u003cbr /\u003e\r\n\t400 1100\u003cbr /\u003e\r\n\t1700 600\u003cbr /\u003e\r\n\t1500 800\u003cbr /\u003e\r\n\t2100 300\u003cbr /\u003e\r\n\t1800 700\u003cbr /\u003e\r\n\t2400 500\u003cbr /\u003e\r\n\t2\u003cbr /\u003e\r\n\t0 1000\u003cbr /\u003e\r\n\t1000 0\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t1446.34\u003cbr /\u003e\r\n\t1414.21\u003c/p\u003e"}}]}