#P9845. [ICPC 2021 Nanjing R] Paimon Polygon

    ID: 11088 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>计算几何2021Special JudgeO2优化凸包ICPC南京

[ICPC 2021 Nanjing R] Paimon Polygon

题目描述

Paimon just puts (n+1)(n+1) distinct points on the plane, one of which is a special point O=(0,0)O=(0,0), and denote the group of remaining points as S\mathbb{S}.

We call a point set U\mathbb{U} strict convex set\textit{strict convex set}, if and only if U3|\mathbb{U}| \ge 3 and all the points from U\mathbb{U} lie exactly on the convex hull built from U\mathbb{U}, with no three points lying on the same line.

You should divide S\mathbb{S} into two sets A\mathbb{A} and B\mathbb{B} so that:

  • AB=\mathbb{A} \cap \mathbb{B}=\emptyset.
  • AB=S\mathbb{A} \cup \mathbb{B}=\mathbb{S}.
  • A2,B2|\mathbb{A}| \ge 2, |\mathbb{B}| \ge 2.
  • The point set A{O}\mathbb{A} \cup \{O\} is a strict convex set\textit{strict convex set}, and denote its convex hull as CA{O}C_{\mathbb{A} \cup \{O\}}.
  • The point set B{O}\mathbb{B} \cup \{O\} is a strict convex set\textit{strict convex set}, and denote its convex hull as CB{O}C_{\mathbb{B} \cup \{O\}}.
  • The outlines(edges) of CA{O}C_{\mathbb{A} \cup \{O\}} and CB{O}C_{\mathbb{B} \cup \{O\}} only intersect at point OO. That is, only one point OO satisfies that it lies both on the outlines of CA{O}C_{\mathbb{A} \cup \{O\}} and CB{O}C_{\mathbb{B} \cup \{O\}}.

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

输入格式

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains one integer nn (4n5×1054 \le n \le 5 \times 10^5) indicating the number of points in S\mathbb{S}.

For the following nn lines, the ii-th line contains two integers xix_i and yiy_i (109xi,yi109-10^9 \le x_i, y_i \le 10^9, (xi,yi)(0,0)(x_i, y_i) \ne (0, 0)) indicating the location of the ii-th point in S\mathbb{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 nn of all test cases will not exceed 10610^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 instead.

Your answer will be accepted if the relative or absolute error is less than 10610^{-6}.

3
4
0 3
3 0
2 3
3 2
5
4 0
5 -5
-4 -2
1 -2
-5 -2
4
0 1
1 0
0 2
1 1

17.2111025509
36.6326947621
0.0000000000

提示

A valid division (left) and an invalid division (right) of the first sample test case are shown below.