Problem F
Greedy Polygons Revisited

MAPS 2020 included a problem named “Greedy Polygons” that described a dystopian world in which the greed that often characterizes human nature had spread to regular polygons, causing these normally well-behaved shapes to exhibit expansionistic tendencies. Now, as feared, this avarice has advanced further, infecting all convex polygons.

In the past, the area of a convex polygon was fixed, but now, whenever it gets the chance, a convex polygon will carry out an expansion operation informally known as a “land grab.” A land grab with expansion distance $d > 0$ works as follows: every point outside the polygon that is at most distance $d$ from some point in the polygon is absorbed and becomes part of the enlarged polygon. (For our purposes, a polygon includes its interior, i.e., it is a solid shape.) Over time, a convex polygon might carry out many land grabs. (Technically, a convex polygon ceases to be a convex polygon (or any kind of polygon at all) after the first land grab, but, alas, such is the distorting effect of greed.)

Given an initial convex polygon and an expansion distance $d$, what is the area of the resulting region after a specified number of land grabs?

Figure $1$ depicts Sample Input $1$, which describes a $5$-sided convex polygon that carries out $2$ land grabs.

\includegraphics[width=0.25\textwidth ]{poly}
Figure 1: Illustration of Sample Input $1$


The first line of input contains three space-separated integers, $n, d, g$, where $n$ is the number of convex polygon vertices $(3 \leq n \leq 60)$, $d$ is the expansion distance $(1 \leq d \leq 10)$, and $g$ is the number of land grabs $(0 \leq g \leq 20)$. This is followed by $n$ lines, each of which contains two space-separated integers, the $x$ and $y$ coordinates, respectively, of one of the polygon vertices. Each coordinate is in the interval $[-1\, 000, 1\, 000]$. The $n$ vertices are distinct, and are given in no particular order. It is guaranteed that no $3$ vertices are collinear.


Output the area of the region occupied by the convex polygon after $g$ land grabs. Your answer will be considered correct if it is within $10^{-3}$ of the official answer.

Sample Input 1 Sample Output 1
5 1 2
0 4
2 2
2 -2
-2 -2
-2 2

Please log in to submit a solution to this problem

Log in