Paimon Polygon

题号：NC234134
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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 $S$ .

We call a point set $U$ strict convex set, if and only if $|U|≥3$ and all the points from $U$ lie exactly on the convex hull built from $U$ , with no three points lying on the same line.

You should divide $S$ into two sets $A$ and $B$ so that:

$A∩B=∅.$
$A∪B=S.$
$|A|≥2,|B|≥2.$
The point set $A∪\{O\}$ is a strict convex set, and denote its convex hull as $C_{A∪\{O\}}$ .
The point set $B∪\{O\}$ is a strict convex set, and denote its convex hull as $C_{B∪\{O\}}$ .
The outlines(edges) of $C_{A∪\{O\}}$ and $C_{B∪\{O\}}$ only intersect at point $O$ . That is, only one point $O$ satisfies that it lies both on the outlines of $C_{A∪\{O\}}$ and $C_{B∪\{O\}}$ .

Please help Paimon to maximize the sum of the perimeters of these two convex hulls. That is, find a valid division $A$ and $B$ which maximizes $(L(C_{A∪\{O\}})+L(C_{B∪\{O\}}))$ , where $L(polygon)$ means the perimeter of that polygon.

输入描述:

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:

The first line contains one integer $n (4≤n≤5×10^5)$ indicating the number of points in $S$ .

For the following n lines, the $i-th$ line contains two integers $x_i$ and $y_i (−10^9≤x_i,y_i≤10^9, (x_i,y_i)≠(0,0))$ indicating the location of the $i-th$ point in $S$ .

It'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.

It's also guaranteed that the sum of n of all test cases will not exceed $10^6$ .

输出描述:

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" (without quotes) instead.

Your answer will be accepted if the relative or absolute error is less than .

示例1

输入

复制

输出

复制

17.2111025509
36.6326947621
0.0000000000