Problem B
Canyon Mapping
Canyons are deep ravines between escarpments or cliffs. They exist on more than just Earth. For example, Valles Marineris on Mars is a vast canyon system running along the Martian equator and is roughly the size of the United States.
Working for a prestigious mapping company, you’ve been tasked with making maps for such canyons. A canyon can be represented in 2D by a simple polygon outline. The maps you will be constructing will be perfectly square and axis aligned. This is due to the mapping company’s desire that tops of their maps are always North. In order to increase the detail, sometimes multiple maps are used to cover just one canyon. Such a collection is called a mapping system. The mapping system of the canyon must cover the entire area of the canyon. The maps in the mapping system must also be the same scale with respect to the canyon and the same size with respect to their printing. This allows the maps to be easily compared when viewed together.
Your mapping system will have exactly $k$ maps. You need to find a mapping system that completely covers the canyon, but each map covers as little area as possible, since a map with less area can be shown at a higher detail. All of the maps must be perfectly square, and must cover the same amount of area on the canyon. The maps can overlap. Since area is the square of side length, just output the side length for simplicity. If things go well enough, your mapping system may even be used to map Valles Marineris in the near future.
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input begins with a line with two space-separated integers $n$ ($3 \le n \le 2\, 000$) and $k$ ($1 \le k \le 3$), where $n$ is the number of vertices in the polygon, and $k$ is the number of square maps in the mapping system. The next $n$ lines each contain two space-separated integers $x$ $y$ ($-20\, 000 \le x, y \le 20\, 000$). These are the coordinates of the polygon, in order. No two edges of the polygon will intersect. All points will be distinct. No three consecutive points will be collinear. The polygon will be a simple polygon which does not touch or cross itself. It will not be degenerate, and will have positive area.
Output
Output a real number rounded to exactly two decimal places, representing the minimum side length with respect to the canyon for each square map in your mapping system, where the maps are identically sized, as small as possible, and the system still covers the entire canyon.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 1 1 5 1 5 5 4 2 |
4.00 |
Sample Input 2 | Sample Output 2 |
---|---|
6 3 -8 -8 0 -1 8 -8 1 0 0 10 -1 0 |
9.00 |
Sample Input 3 | Sample Output 3 |
---|---|
16 2 0 0 3 0 3 3 6 3 8 0 10 4 10 10 8 10 8 6 6 10 6 11 5 9 4 7 3 11 2 1 0 4 |
9.00 |