Basics of plane geometry
You are given N points on the plane. Each point is either red or blue. You need to find non-self-intersecting polygon separating points of two colors. So that all red points are inside or on the border of the polygon, and all blue points are outside or on the border of the polygon, or vice versa. The goal is to minimize the perimeter of your polygon.
As mentioned in a hint the simplest way to get AC is to construct a polygon simply having all N points on its boundary. We consider several ways how to do this.
Let’s sort all points in lexicographical order (at first by X-coordinate and in the case of a tie by Y-coordinate). Actually it is almost correct just to print this sorted array of points as the answer. Indeed, it will be non-self-intersecting except that the last side, that connects the first and the last vertexes, could intersect many other sides. To handle this issue it is sufficient to add just two points to the end of this list. Namely, the points (maxX, maxY + 1) and (minX − 1, maxY + 1) will do the job, where minX is the minimal X-coordinate among all points and maxX, maxY are defined similarly. Just draw the corresponding picture to the following example (it is already sorted):
Two additional points will be (3, 4) and (0, 4). Note that we exclude point (3, 3). This is to show necessity of the point (maxX, maxY + 1). Without adding this point you get self-intersection here. And actually you indeed get WA adding only the point (minX − 1, maxY + 1) to the end of the list. Also note that the point (minX, maxY + 1) instead of (minX − 1, maxY + 1) also leads to WA as the last side can completely cover the first side in this case (again refer to this example). See tester’s 1st solution as a reference to this approach. But such solution scores only 23.721313 points (note that ACRush was able to score less than 4.000 points!)
Actually, we could print only input points in some order to get AC. For this let’s choose some point inside or on the boundary of the convex hull of all our points, and sort them by the polar angle with respect to this point making some careful consideration of the points with the same polar angle. One of the simplest way to get AC by this scheme is to choose the point with the coordinates (sumX / N, sumY / N), where sumX is the sum of X-coordinates of all the points and sumY is the sum of Y-coordinates of all the points. Clearly, this point lies inside or on the boundary of the convex hull. Also this point is quite lucky and we should not care about the order of the points with the same angle. Simply sorting pairs (angle, index) and printing points in the order that this sorted arrays produces gets AC. And such solution gives slightly better score 14.734905. Refer to the tester’s 2nd solution for details.
Let’s play with the previous solution to achieve better score. Let’s choose some random convex linear combination of input points and sort all points with respect to this point. Doing this many times (namely, while time permits) we could seek for the polygon with the smallest perimeter. To construct convex linear combination of points
(X[i], Y[i]), i = 1, 2, …, N,
we choose some sequence of non-negative weights
w, w, …, w[N]
and consider the point of the form
(sumX / sumW, sumY / sumW), where
sumX = w * X + … + w[N] * X[N],
sumY = w * Y + … + w[N] * Y[N],
sumW = w + … + w[N].
Such solution scores 13.651408. Refer to the tester’s 3rd solution for details. Note how the comparison of points by polar angle is performed there. It is recommended way how it should be always made.
The problem is NP-complete since we can reduce the classical NP-complete traveling salesman problem to it. For this we should take equal number of red and blue points and place them by pairs where in each pair we have one red and one blue point that are very close to each other. Than any polygon that separates points of different color should approximately have vertexes close to the points in pairs. So it will correspond to traveling salesman tour.
We can use this insight to achieve slightly better score. We still ignore colors of vertexes and simply seek for the traveling salesman tour that passes through each of our points exactly once. There are many approximate algorithms exist for this problem.
The fairly simple one was implemented by Rudradev Basak in his first solution. Namely, he chooses some random permutation as a route and then check for each pair of non-consecutive sides AB and CD whether we could improve the perimeter of the polygon by reversing the path from B to C, so that we replace |AB| + |CD| by |AC| + |BD| in the perimeter. It can be proved that once no such improvements are possible then we have non-self-intersecting polygon. This idea brings him 6.70761 points. Refer to the tester’s 4th solution as a clean and commented version of the described solution that also tries permutations while time permits, which allows to get a better score 6.428542.
ADVENTURES WITH SPECIAL JUDGE LEADING TO CONTEST EXTENSION:
Just 3 hours before the scheduled end of the contest, we received the new best solution by Rudradev Basak which scores only 3.614238 points, while ACRush was the only one who was able to score less than 4 points at that time and his score was about 3.99. Analyzing Rudradev’s submission we noticed that he simply uses the scheme above, adjusting the permutation, but only for points of some color (actually he tries both colors and also does this while time permits). So, his output is simply the polygon that contains points of one of the colors. Clearly, in general for such polygon we could have points of other color inside as well as outside it. So this output is wrong. David quickly realized the error in the special judge and fixed it by adding one addition check for such case. This happened just in half an hour before scheduled end of the contest. In mere minutes we made a decision to rejudge all AC submissions and extend the contest one day more. The actual extension was made just in 6 minutes before the scheduled end of the contest. Apparently, the last half an hour of the contest was insane for us.
You may find interesting to see how Rudradev was able to figure out our bug:
“It was a very unexpected combination of events that led me to the find the bug:
1) I made the same bug in my local tester as the online judge.
2) The logic for my solution happens to trigger the bug, but in a non trivial fashion. When I realized the above, I made a very simple change to the code which would make it absolutely clear if the online judge indeed has the same bug.
3) I submit this changed code, but I happen to submit it on a wrong problem, and getting WA, think that I might be mistaken about above.
4) Few hours later I happen to look at my KILOWHAT submission history, and am surprised to see no WA there.
5) Figure out everything, make the joke submit, and behold!
In any case, extending the contest was the right thing to do. Unfortunately I won’t have any time at all to work on this problem in the next 24 hrs.”
The author’s solution does not ignore colors and construct some non-trivial polygon that separates points of different colors, which allows to score 5.515622 in no time. It starts with an edge that will belong to the result, a set of points that will be inside the result polygon, and a set of points that will be outside. It begins by finding the convex hull of the “inside” points, then for each point inside, it assigns it to the nearest edge. Then for each edge it applies the algorithm recursively, swapping inside and outside points. It combines the sub-results into a single polygon. See author’s solution for implementation details and additional comments for understanding this approach. Probably adding some randomizations and running it while time permits could allow getting closer to unbeatable ACRush
AUTHOR’S AND TESTER’S SOLUTIONS:
|Author's solution||can be found here. It scores 5.515622 points using 0.00 of time.|
|Tester's 1st solution||can be found here. It scores 23.721313 points using 0.00 of time.|
|Tester's 2nd solution||can be found here. It scores 14.734905 points using 0.00 of time.|
|Tester's 3rd solution||can be found here. It scores 13.651408 points using 0.98 of time per test.|
|Tester's 4th solution||can be found here. It scores 6.428542 points using 0.99 of time per test.|
Will be provided soon. All readers are welcomed to provide related problems in comments.