Let your spirit soar and have a joy-filled new year by playing Ghenshin :D
However, before that, I will recommend to you an interesting "Genshin Geometry" problem
(Problem F from the GYM The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)).
Summary: Give N distint points on the plane, and special point O = (0, 0). Your task is dividing this N points into two sets A and B so that:
Both of them is a strict convex set.
The outlines(edge) of two convex hulls only intersect at point O.
The sum of the perimeters of these two convex hulls is maximum.
So now, let's try to solve this problem by yourself...
.
.
.
.
.
.
.
.
.
.
.
.
.
....before reading some hints!
Firstly, let's answer this question: Is there any TRICKS to contruct these two sets optimally directly ?. (It becomes a Greedy problem!!!). In my opinion, this problem has a lot of cases, and the greedy solution is difficult to approach. So, I will representation a general solution, but if you have a more optimal solution, please leave your commend and everyone can reference.
This problem has two general case. The first case is easier to approach: convex hull covers convex hull.
So, set A is the convex hull of N points , and there are M remaining points that do not lie on this convex hull. Obviously, these M points are belong to the set B. Note, we need to check if remaining M points is strict convex and don't forget to the point O. Of course, finding convex hull is within O(NlogN)
But wait, is there any special cases?
The second case is dividing line.
The line connecting point O and any other point divides these N points into two groups. For more clearly, see this
So, the solution is: For each point, divide N points with line connecting point O and that point into two groups, check if these groups are convex and find the maximum perimeters of all such dividing. But,
