#P9845. [ICPC 2021 Nanjing R] Paimon Polygon
[ICPC 2021 Nanjing R] Paimon Polygon
题目描述
Paimon just puts distinct points on the plane, one of which is a special point , and denote the group of remaining points as .
We call a point set , if and only if and all the points from lie exactly on the convex hull built from , with no three points lying on the same line.
You should divide into two sets and so that:
- .
- .
- .
- The point set is a , and denote its convex hull as .
- The point set is a , and denote its convex hull as .
- The outlines(edges) of and only intersect at point . That is, only one point satisfies that it lies both on the outlines of and .
Please help Paimon to maximize the sum of the perimeters of these two convex hulls. That is, find a valid division and which maximizes $(L(C_{\mathbb{A} \cup \{O\}}) + L(C_{\mathbb{B} \cup \{O\}}))$, where means the perimeter of that polygon.
输入格式
There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:
The first line contains one integer () indicating the number of points in .
For the following lines, the -th line contains two integers and (, ) indicating the location of the -th point in .
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 of all test cases will not exceed .
输出格式
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 .
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.