---------- Spike is a bounty hunter and he is currently tracking a criminal! To investigate he uses his spaceship, the Swordfish II, and travels to $N$ different places on 2D Euclidean space before returning to his crew at the starting location with all the information he has gathered. The starting location is the leftmost place (with the lowest $x$-coordinate) and Spike wants to travel to every other place before returning. However space fuel costs a lot of Woolongs and Spike would rather spend his money on special beef with bell peppers. Therefore he wants to travel the minimum possible distance. On top of that he is being chased by the Red Dragon crime syndicate. To make sure they don’t catch him he can only visit places in increasing order of their $x$-coordinate until he reaches the rightmost place (with the largest $x$-coordinate), then he can turn around and visit places in decreasing order of their $x$-coordinate until he reaches his starting location again. # Input The input starts with an integer $T$ ($1 \le T \le 100$) specifying the number of test cases that follow. Each test case consists of an integer $N$ ($2 \le N \le 512$) specifying the number of places in the tour. The coordinates of these places are given as integers in the next $N$ lines, $x$-coordinate first, $y$-coordinate second ($0 \le x, y \le 5000$). The places are given in ascending order of the $x$-coordinate. Every place has a unique $x$-coordinate. # Output For each test case, output on a single line the minimum travel distance needed to complete the tour. Your output should have an absolute or relative error of at most $10^{-2}$. ## Sample Input ``` 2 5 0 1 1 2 2 0 3 2 4 1 3 100 1 200 1 300 1 ``` ## Sample Output ``` 9.300563079746 400 ``` ---------------------------------- <details class="blue"> <summary> راهنمایی ۱ </summary> در واقع سوال از ما می‌خواهد که به غیر از عنصر اول و آخر بقیه را به دو زیر دنباله افراز کنیم،‌ سپس هر دو عنصر اول و آخر به اول و آخر هر دو دنباله اضافه کنیم و در نهایت طولی که برای پیمودن این دو دنباله نیاز است را با هم جمع بزنیم. به طور مشخص تعداد حالت‌های افراز دنباله‌ی اصلی به دو دنباله بسیار زیاد است و نمی‌توان روی همه‌ی حالات رفت ولی اگر یک ترتیب نظام‌مند برای حرکت روی دنباله‌ و افراز آن به دو دنباله‌ی مشخص داشته باشیم، می‌توانیم از برنامه‌نویسی پویا برای به دست‌ آوردن پاسخ استفاده کنیم. </details> ---------------------------------- <details class="blue"> <summary> راهنمایی ۲ </summary> از پایین به بالا (به صورت صعودی بر حسب $x$) حرکت می‌کنیم و اندیس آخرین نقطه‌ی هر دو دنباله را در استیت $dp$ ذخیره کرده و عنصر جدید را به یکی از آن‌ها اضافه می‌کنیم. به طور دقیق‌تر، $dp[i][j]$ که در آن $j < i$ است را بدین صورت تعریف می‌کنیم: کل $i$ نقطه‌ی اول را در نظر گرفته و می‌دانیم که دنباله‌ای که با شروع از نقطه‌ی اول به نقطه‌ی آخر می‌رسد از ما عبور می‌کند و همچنین آخرین نقطه‌ای (نقطه‌ای که بزرگترین $x$ را دارد) که در مسیر برگشت قرار دارد، $j$ می‌باشد. حال با رعایت تمام این شرایط، حداقل هزینه‌ی رسیدن از نقطه‌ی شروع به راس $i$ام به علاوه‌ی حداقل هزینه برای رسیدن از نقطه‌ی $j$ام به نقطه‌ی شروع را داخل $dp[i][j]$ می‌ریزیم. استیت‌های $dp$ از $O({n^2})$ است و از هر استیت هم دقیقا دو نفر مشخص اپدیت می‌شوند. به طور دقیق‌تر، $dp[i][j]$ پس از اضافه کردن یک عنصر به آن، یا به استیت $dp[i + 1][j]$ می‌رود و یا به $dp[i + 1][i]$ (می‌توانیم جای دو دنباله را عوض کنیم چون طول را چه از اول به آخر و چه برعکس به دست بیاوریم با هم برابر است). بنابراین در مجموع الگوریتم ما از $O({n^2})$ می‌باشد. در نهایت نیز برای به دست‌آوردن به ازای همه‌ی $1 <= j <= n$ مقدار جواب را با مقدار $dp[n][j] + dis(n, j)$ مینیمم می‌گیریم که در آن $dis(i, j)$ نمایانگر فاصله‌ی اقلیدسی نقطه‌ی $i$ام و نقطه‌ی $j$ام می‌باشد. </details>

B: Hunter

Spike is a bounty hunter and he is currently tracking a criminal! To investigate he uses his spaceship, the Swordfish II, and travels to $N$ different places on 2D Euclidean space before returning to his crew at the starting location with all the information he has gathered. The starting location is the leftmost place (with the lowest $x$ -coordinate) and Spike wants to travel to every other place before returning. However space fuel costs a lot of Woolongs and Spike would rather spend his money on special beef with bell peppers. Therefore he wants to travel the minimum possible distance.

On top of that he is being chased by the Red Dragon crime syndicate. To make sure they don’t catch him he can only visit places in increasing order of their $x$ -coordinate until he reaches the rightmost place (with the largest $x$ -coordinate), then he can turn around and visit places in decreasing order of their $x$ -coordinate until he reaches his starting location again.

Input🔗

The input starts with an integer $T$ ( $1 \le T \le 100$ ) specifying the number of test cases that follow.

Each test case consists of an integer $N$ ( $2 \le N \le 512$ ) specifying the number of places in the tour. The coordinates of these places are given as integers in the next $N$ lines, $x$ -coordinate first, $y$ -coordinate second ( $0 \le x, y \le 5000$ ). The places are given in ascending order of the $x$ -coordinate.

Every place has a unique $x$ -coordinate.

Output🔗

For each test case, output on a single line the minimum travel distance needed to complete the tour. Your output should have an absolute or relative error of at most $10^{-2}$ .

Sample Input🔗

Sample Output🔗

9.300563079746
400

راهنمایی ۱

در واقع سوال از ما می‌خواهد که به غیر از عنصر اول و آخر بقیه را به دو زیر دنباله افراز کنیم،‌ سپس هر دو عنصر اول و آخر به اول و آخر هر دو دنباله اضافه کنیم و در نهایت طولی که برای پیمودن این دو دنباله نیاز است را با هم جمع بزنیم.

به طور مشخص تعداد حالت‌های افراز دنباله‌ی اصلی به دو دنباله بسیار زیاد است و نمی‌توان روی همه‌ی حالات رفت ولی اگر یک ترتیب نظام‌مند برای حرکت روی دنباله‌ و افراز آن به دو دنباله‌ی مشخص داشته باشیم، می‌توانیم از برنامه‌نویسی پویا برای به دست‌ آوردن پاسخ استفاده کنیم.

راهنمایی ۲

از پایین به بالا (به صورت صعودی بر حسب $x$ ) حرکت می‌کنیم و اندیس آخرین نقطه‌ی هر دو دنباله را در استیت $dp$ ذخیره کرده و عنصر جدید را به یکی از آن‌ها اضافه می‌کنیم. به طور دقیق‌تر، $dp[i][j]$ که در آن $j < i$ است را بدین صورت تعریف می‌کنیم:

کل $i$ نقطه‌ی اول را در نظر گرفته و می‌دانیم که دنباله‌ای که با شروع از نقطه‌ی اول به نقطه‌ی آخر می‌رسد از ما عبور می‌کند و همچنین آخرین نقطه‌ای (نقطه‌ای که بزرگترین $x$ را دارد) که در مسیر برگشت قرار دارد، $j$ می‌باشد. حال با رعایت تمام این شرایط، حداقل هزینه‌ی رسیدن از نقطه‌ی شروع به راس $i$ ام به علاوه‌ی حداقل هزینه برای رسیدن از نقطه‌ی $j$ ام به نقطه‌ی شروع را داخل $dp[i][j]$ می‌ریزیم.

استیت‌های $dp$ از $O({n^2})$ است و از هر استیت هم دقیقا دو نفر مشخص اپدیت می‌شوند. به طور دقیق‌تر، $dp[i][j]$ پس از اضافه کردن یک عنصر به آن، یا به استیت $dp[i + 1][j]$ می‌رود و یا به $dp[i + 1][i]$ (می‌توانیم جای دو دنباله را عوض کنیم چون طول را چه از اول به آخر و چه برعکس به دست بیاوریم با هم برابر است).

بنابراین در مجموع الگوریتم ما از $O({n^2})$ می‌باشد. در نهایت نیز برای به دست‌آوردن به ازای همه‌ی $1 <= j <= n$ مقدار جواب را با مقدار $dp[n][j] + dis(n, j)$ مینیمم می‌گیریم که در آن $dis(i, j)$ نمایانگر فاصله‌ی اقلیدسی نقطه‌ی $i$ ام و نقطه‌ی $j$ ام می‌باشد.