### MutedSolace's blog

By MutedSolace, history, 2 months ago,

I think this problem simplifies down to putting k elements into 2 sets given conditions in the format of either:
1. x and y cannot both be in set 1
2. x and y cannot both be in set 2
where set 1 represents lamps oriented vertically and set 2 represents lamps oriented horizontally.

So far I have tried a bfs bipartite-like approach but it's getting WA on TC 9/43:

My Code

Any help would be appreciated!

• +1

By MutedSolace, history, 4 months ago,

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.

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.

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.

• -1