I: Polygon Game

https://open.kattis.com/problems/polygongame

• The main observation is that the final number of pieces in the polygon cannot be too big!

• Even though each of the $m$ lines (cuts) has the potential to cut each polygon into two pieces (which might suggest that you can form $2^m$pieces), the total number of pieces is actually at most $\frac{m \cdot (m+1)}{2}+1$.

Try proving this upper bound! To gain some intuition, for $m=2$ you can divide the plane into $4$ regions. However, you cannot get $8$ regions using $3$ lines. The maximum number of regions you can create with $3$ lines is $7$.

• Now, we can just simulate the polygon cutting process, which can be implemented trivially once we have primitives such as computing line intersections.

  • Maintain a list of existing polygons.

  • At each iteration, intersect the line with every polygon in the existing list.

  • Replace the list of polygons with the new (potentially) smaller polygons created in this iteration.

• Finally, iterate through all the polygons that remain in the end, and report the maximum area.