Problem link: https://open.kattis.com/problems/enclosure
I would appreciate any help on this! I have spent three separate sessions working on this problem. ICPC Regional solutions are either rare or nonexistent as far as I know :'(
Summary: You have k points out of n. Choose one point out of the remaining (n – k) such that the convex hull of the k + 1 points is maximized.
In my opinion the "worst case" is k = 50 000 and n = 100 000. Brute forcing the convex hull for each point directly is too slow since one would have to construct the convex hull 50 thousand times.
Naturally, I looked at the convex hull of the k points instead. The shoelace theorem can get the area of it, and then if I can examine each point's added area fast enough, I can keep track of the maximum area added. From there I can add that to the initial area to get the final answer. For polygons with few sides, it's easy to see what the resulting convex hull would be. For example, if the initial convex hull is a triangle, there are areas where adding a point only needs one additional triangle, and others were adding a point needs two additional triangles. However, for shapes with more sides, the number of triangles required to add can range from 0 to (k – 1). Re-adjusting the shoelace theorem would take too long (start from original, take out a chunk of points and replace it with the new point). I don't see how prefix sums could solve this issue either since if the point is below "p0" in the convex hull, the prefix sum doesn't wrap around. Maybe segment trees that somehow wrap around? (I'm not familiar enough with them)
Resources/Notes: Graham Scan sorts the points in polar angle in relation to p0 (bottom-most point, tiebreaks broken by left-most). This allows the shoelace formula to be applied, since the points are in clockwise counter-clockwise order. From here "point-in-triangle" formula after binary searching which angles the new point might be between allows checking "inside the convex hull" in log n time. No three points are collinear. Heron's formula is nice for computing the area of a triangle given coordinates, though might not be as useful here since multiple triangles might have to be added.
Other Theories: Vertex Average/Center of Mass, try the points farthest away (probably doesn't work since some points closer to CoM could be outside the convex hull while some points further away aren't?) Looking at the prefix sums again, to calculate wrap-around all I would have to do is take the appropriate left side and right side segments. Also, I could binary search which points have to have to be taken out in the new convex hull. If the prefix sums do allow me to update the shoelace formula in o(1) then I would be in the clear... k log k for initial convex hull construction, and (n – k) * log(k) to calculate each area for overall x log x-ish runtime, which is good for 100 thousand.
Other relevant links: convex hull, shoelace theorem, point in polygon + explicit formula for point in triangle https://cp-algorithms.com/geometry/convex-hull.html https://artofproblemsolving.com/wiki/index.php/Shoelace_Theorem https://cp-algorithms.com/geometry/point-in-convex-polygon.html
I think I'm missing something crucial here, perhaps in the approach or observations.
Thanks in advance!
PS: I feel terrible posting this now that I have a theory that might work (see second 'other theory'), but I have finals incoming and cannot work on this problem for a few days. I would love a second opinion or set of eyes on this.
