Hide

Problem D
Enclosure

In the Dark Forest, you control some trees. The territory you control is defined by the smallest convex shape that contains all of the trees that you control. Your power is defined by the area of this convex shape. You may control trees inside the convex shape that are not on the edge of the shape.

You currently control $k$ trees of the $n$ in the forest. You want to extend your power by gaining control over a single additional tree, somewhere in the forest. After acquiring the single tree that most increases your power, what is the area of your new shape?

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two space-separated integers $n$ and $k$ ($3 \le k < n \le 100\, 000$), where $n$ is the total number of trees, and $k$ is the number of trees that you control.

The next $n$ lines each have two space-separated integers $x$ and $y$ ($-10^9 \le x, y \le 10^9$) specifying the locations of the $n$ trees. The first $k$ trees in the list are the trees that you control. No three trees will have collinear locations. Note that there may be trees that you do not control within your shape.

Output

Output a single real number, which is the largest area you can achieve by controlling a single additional tree. Output this number to exactly one decimal place.

Sample Input 1 Sample Output 1
5 3
-5 -5
-5 5
5 -5
-4 6
5 5
100.0

Please log in to submit a solution to this problem

Log in