UChicago Practice Contest 2018-04-28


2018-04-28 17:00 UTC

UChicago Practice Contest 2018-04-28


2018-04-28 22:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -331 days 5:05:32

Time elapsed


Time remaining


Problem D

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?


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 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