# I: Polygon Game

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/i-polygon-game.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.