Under construction

Still being built. Things may change

Not Too Convex Hull

Time limit1sMemory limit128 MB

Summary
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 BB rubber bands. The challenge is to use the BB rubber bands to wrap the nails so that:

  1. each rubber band wraps a subset of the nails;
  2. every nail is inside some wrapping;
  3. the wrappings do not overlap one another, except at the Origin nail, which is touched by all of the rubber bands;
  4. each rubber band forms a wrapping that is a convex polygon with at least three corners;
  5. 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

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 BB and NN, giving respectively the number of rubber bands and the number of nails, with 2≤B≤502 \le B \le 50 and 2B+1≤N≤1012B+1 \le N \le 101. The following NN lines describe the positions of the nails; each line contains two integers XX and YY (−10000≤X,Y≤10000-10000 \le X, Y \le 10000). The Origin is the first nail in the input. The end of input is indicated by B=N=0B = N = 0.

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.

Examples3

  1. Example 1

    Input
    2 5
    0 0
    9 4
    -8 8
    -10 -2
    4 -8
    2 6
    0 0
    3 6
    -5 7
    -4 -6
    10 -10
    3 5
    0 0
    
    Expected output
    92.00
    74.00
    
  2. Example 2

    Input
    2 5
    0 0
    9 17
    14 -24
    8 11
    -15 -13
    0 0
    
    Expected output
    242.00
    
  3. Example 3

    Input
    2 6
    0 0
    15 14
    -12 15
    12 -17
    -9 -4
    -4 15
    0 0
    
    Expected output
    301.00