> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/i-polygon-game.md).

# 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$$.

{% hint style="info" %}
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$$.
{% endhint %}

* 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.