{"problem":{"name":"[ICPC 2021 Nanjing R] Paimon Polygon","description":{"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}$. We call a point set $\\mathbb{U}$ $\\textit{s","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9845"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThere 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$.\n\n## Output\n\nFor 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}$.\n\n[samples]\n\n## Note\n\nA 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)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9845","tags":["计算几何","2021","Special Judge","O2优化","凸包","ICPC","南京"],"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"]],"created_at":"2026-03-03 11:09:25"}}