A topic that I have come up with, which I personally think is quite interesting, but its feasibility is unknown.
First Of All,If the solution provider can provide ideas and code and can verify the correctness (of course, I will try my best to hack your solution, of course, I will give you the corresponding data range according to your practice, and such polygon points should exceed a certain number, perhaps more than 10 points, with a certain adaptability), if you are a Codeforces Coder in Chinese Mainland, I will contact you and give you rand (100-300) RMB to thank you for your contribution. (Although this is not a high sum of money, it contains my persistence in this problem. I will give a certain amount of money based on the superiority of the solution)
If you are a non Chinese Mainland player, I will try my best to give you a reward.
Question description:
Here is an arbitrary polygon, with each corner size ranging from 0 to 360 degrees. I hope you can find a strictly convex polygon that is completely contained within this polygon, so that the area of this convex polygon is maximized. You only need to calculate the value of this area.
Of course, since I don't have any effective methods, and I can't determine which interval corresponds to the correct method for the number of points in this polygon. But I'll give you some pictures to understand the meaning of this question.
If the two polygons given in this figure are assumed to be the same, then both extraction schemes for convex polygons may be optimal. Is there a universal construction algorithm or other technology that can solve this problem?
As shown in the figure, the definition of a convex hull is that for a polygon, the degree of each interior angle is between 0 and 180 degrees.
Here are some other examples as well：
Perhaps the efficiency and adaptability of certain solutions may be related to the number of concave angles, the number of polygon points, even the sum of interior angles, the intersection of inscribed circles and half planes, or some may simply be interference.
Perhaps my computational geometry is not profound enough, and I hardly believe that there is a solution to this problem.If you don't like this question, please don't Downvote. Thank you~
Auto comment: topic has been updated by Teatify (previous revision, new revision, compare).
Auto comment: topic has been updated by Teatify (previous revision, new revision, compare).
Auto comment: topic has been updated by Teatify (previous revision, new revision, compare).
Auto comment: topic has been updated by Teatify (previous revision, new revision, compare).
Auto comment: topic has been updated by Teatify (previous revision, new revision, compare).
I think you might be interested in this.
orz
Wow, this looks more like a pure geometry problem. I think this is very rare in computational geometry for algorithm competitions. I was already interested in Euclidean geometry before playing Codeforces. Let me think about how to implement this algorithm? The platform you provided is very good, and I should thank you well no matter what~
jeroenodb he is a geometrician.
Delft is also a site of Universal Cup, perhaps we can get ideas from him~
Looking at the figures, it reminds me of the problem https://qoj.ac/contest/442/problem/1196.
The idea would be to take any segment and make right turns until the figure is closed.
This ensures that the result is a convex polygon contained within the original one, and by doing so on each edge, we ensure finding the maximum area.
In the near future, I would like to create a tutorial of this problem.
Orz，But this problem is relatively simpler. I also encountered this problem last month. I see that you are also very interested in geometry and have solved many geometric problems in some virtual competitions.
Actually, it seems much more difficult to me. I was thinking of some sort of star where the polygon that maximizes its area doesn't pass through any edge. Thinking about finding some parameter to construct the solution when a point is reached, it would be necessary to decide between certain "visible" points to move towards and probably use DP to avoid exponential complexity. And yes, I love geometry and enjoy making difficult problems; in my opinion, it's the best way to improve, with the goal of achieving something in ICPC. If you'd like, I can recommend some problems, or better yet, you can recommend me some ^^.
Of course, I am responsible for the computational geometry part of our team. I have seen many interesting problems, but I believe that thinking is still very important. There is a master named Crimson231 on QOJ, and you can take a look at the difficulty of the computational geometry problems he solves on OvO
Errichto is good at computational geometry.
orz