Not Too Convex Hull
Time limit1sMemory limit128 MB
Partition the nails into B convex polygonal groups, all sharing the origin nail, minimizing the total covered area, with the origin strictly inside the global hull.
- Level
Hard9 of 10
- Topics
- Dynamic programming, Geometry, Sorting, Divide and conquer
- Solved
- No attempts yet
Problem
Nails and Rubber Bands. That is the suggestive name of a game played by a group of children (all of them offspring of geometry teachers). The children fix a number of nails on a plank of wood, at random positions. Then they choose one of the nails to be the Origin and prepare rubber bands. The challenge is to use the rubber bands to wrap the nails so that:
- each rubber band wraps a subset of the nails;
- every nail is inside some wrapping;
- the wrappings do not overlap one another, except at the Origin nail, which is touched by all of the rubber bands;
- each rubber band forms a wrapping that is a convex polygon with at least three corners;
- the total area covered by the wrappings is the smallest among all possible ways of wrapping the nails.
An instance of the game is shown in Figure 1.

Figure 1: A game with 19 nails and 2 rubber bands
Input
Your program must solve several instances of the game. Each game description starts with a line containing two integers and , giving respectively the number of rubber bands and the number of nails, with and . The following lines describe the positions of the nails; each line contains two integers and (). The Origin is the first nail in the input. The end of input is indicated by .
In every game in the input:
- no two nails share the same point;
- no three nails lie on the same line;
- the Origin nail does not belong to the convex hull of all the nails; that is, if you use a single rubber band to wrap all the nails it never touches the Origin nail, because the Origin lies strictly inside the hull.
Output
For each game, output a single line with the smallest total area covered by the wrappings. Print the area as a real number with two decimal places, rounding the last digit. The input contains no test cases where rounding differences are significant.