{"raw_statement":[{"iden":"statement","content":"Paimon just puts $(n+1)$ distinct points on the plane, one of which is a special point $O=(0,0)$, and denote the group of remaining points as $\\mathbb{S}$.\n\nWe call a point set $\\mathbb{U}$ $\\textit{strict convex set}$, if and only if $|\\mathbb{U}| \\ge 3$ and all the points from $\\mathbb{U}$ lie exactly on the convex hull built from $\\mathbb{U}$, with no three points lying on the same line.\n\nYou should divide $\\mathbb{S}$ into two sets $\\mathbb{A}$ and $\\mathbb{B}$ so that:\n- $\\mathbb{A} \\cap \\mathbb{B}=\\emptyset$.\n- $\\mathbb{A} \\cup \\mathbb{B}=\\mathbb{S}$.\n- $|\\mathbb{A}| \\ge 2, |\\mathbb{B}| \\ge 2$.\n- The point set $\\mathbb{A} \\cup \\{O\\}$ is a $\\textit{strict convex set}$, and denote its convex hull as $C_{\\mathbb{A} \\cup \\{O\\}}$.\n- The point set $\\mathbb{B} \\cup \\{O\\}$ is a $\\textit{strict convex set}$, and denote its convex hull as $C_{\\mathbb{B} \\cup \\{O\\}}$.\n- The outlines(edges) of $C_{\\mathbb{A} \\cup \\{O\\}}$ and $C_{\\mathbb{B} \\cup \\{O\\}}$ only intersect at point $O$. That is, only one point $O$ satisfies that it lies both on the outlines of $C_{\\mathbb{A} \\cup \\{O\\}}$ and $C_{\\mathbb{B} \\cup \\{O\\}}$.\n\nPlease help Paimon to maximize the sum of the perimeters of these two convex hulls. That is, find a valid division $\\mathbb{A}$ and $\\mathbb{B}$ which maximizes $(L(C_{\\mathbb{A} \\cup \\{O\\}}) + L(C_{\\mathbb{B} \\cup \\{O\\}}))$, where $L(\\text{polygon})$ means the perimeter of that polygon."},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains one integer $n$ ($4 \\le n \\le 5 \\times 10^5$) indicating the number of points in $\\mathbb{S}$.\n\nFor the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \\le x_i, y_i \\le 10^9$, $(x_i, y_i) \\ne (0, 0)$) indicating the location of the $i$-th point in $\\mathbb{S}$.\n\nIt's guaranteed that the points given in the same test case are pairwise different. However, there may be three points lying on the same line.\n\nIt's also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$."},{"iden":"output","content":"For each test case output one line containing a number indicating the maximum total perimeter. If there does not exist a valid division output `0` instead.\n\nYour answer will be accepted if the relative or absolute error is less than $10^{-6}$."},{"iden":"note","content":"A valid division (left) and an invalid division (right) of the first sample test case are shown below.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/v17tmtdh.png)"}],"translated_statement":null,"sample_group":[["3\n4\n0 3\n3 0\n2 3\n3 2\n5\n4 0\n5 -5\n-4 -2\n1 -2\n-5 -2\n4\n0 1\n1 0\n0 2\n1 1\n","17.2111025509\n36.6326947621\n0.0000000000\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}