Problem link: https://open.kattis.com/problems/enclosure

I would appreciate any help on this! 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 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 amount 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 cw (clockwise) or ccw 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?)

Other relevant links: https://cp-algorithms.com/geometry/convex-hull.html https://artofproblemsolving.com/wiki/index.php/Shoelace_Theorem

I think I'm missing something crucial here, perhaps in the approach or observations.

Thanks in advance!