{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003ePakhom stands at the point \u003ci\u003eS\u003c/i\u003e and wants to reach the point \u003ci\u003eT\u003c/i\u003e to buy the land there. But he noticed a gully, which represents a polyline \u003ci\u003eABC\u003c/i\u003e. What is the length of the shortest path Pakhom should walk if he doesn\u0027t want to fall into the gully?\u003c/div\u003e\u003c/div\u003e\u003cimg src\u003d\"CDN_BASE_URL/71cf6493af48a01eb77dade89dfc7716?v\u003d1715949571\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains the number of testcases \u003ci\u003en\u003c/i\u003e (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000). Each of the next \u003ci\u003en\u003c/i\u003e lines contains one testcase. Each testcase is written as 10 space-separated integers: \u003ci\u003ex\u003csub\u003eS\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003eS\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ex\u003csub\u003eT\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003eT\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ex\u003csub\u003eA\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003eA\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ex\u003csub\u003eB\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003eB\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ex\u003csub\u003eC\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003eC\u003c/sub\u003e\u003c/i\u003e, the coordinates of the points \u003ci\u003eS\u003c/i\u003e, \u003ci\u003eT\u003c/i\u003e, \u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e, and \u003ci\u003eC\u003c/i\u003e, respectively. All points within the test case are different. Points \u003ci\u003eS\u003c/i\u003e and \u003ci\u003eT\u003c/i\u003e don\u0027t belong to the polyline \u003ci\u003eABC\u003c/i\u003e. All numbers in test cases don\u0027t exceed 10 by absolute value.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFor each test case output the answer on a separate line. The answer should be precise up to 10\u003csup\u003e−6\u003c/sup\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2 5 6 4 4 5 2 1 6\r\n2 2 4 3 1 3 3 3 3 1\r\n2 1 4 4 3 2 4 3 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.000000\r\n3.650282\r\n3.828427\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}