Codah ClubTrain. Submit. Improve.
Sign in
English
#000089

z-rubberz

There are N trees on a field, and there are no 3 collinear trees. You have K rubber bands that can stretch to an arbitrary length. We will refer to one of the tree as the <b>central tree</b>. The central tree does not belong to the trees on the convex hull of all the trees.


You need to place the K rubber bands around the given trees so that:
(1) Every rubber band contains a group of trees
(2) All the trees are contained in the rubber bands
(3) The rubber bands do not overlap except on the central tree
(4) The rubber bands make convex polygons that contain at least 3 trees


Image: image

For the given configuration of trees, find the configuration of the K rubber bands that satisfies the conditions listed above and minimizes the area that all of them cover (View the image).


InputThe data is read from the standard input. The first line contains two integers K and N (2 <= K <= 50, 1 <= N <= 200), which represent the number of rubber bands and the number of trees. Each of the next N lines contains the two integers X and Y from range [-10.000, 10.000] that represent the coordinates of the trees on the field. The central tree is the first tree listed (the one given on the second line of the standard input).

OutputTo the standard output write the minimal area covered by the rubber bands that satisfies the conditions listed above. You should output the result with two decimal figures.

Input:
2 5
0 0
9 4
-8 8
-10 -2
4 -8
Output:
92.00

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.