Enclosure

Time limit2sMemory limit512 MB

Summary

Given k controlled points forming a convex hull, add one of the remaining points to maximize the hull area, and print the resulting area to one decimal.

Level: Hard8 of 10
Topics: Geometry, Greedy, Sorting, Binary search
Solved: No attempts yet

Problem

In the Dark Forest you control some of the trees. The territory you control is the smallest convex shape that contains every tree you control, and the area of that shape is your power. A tree you control may sit strictly inside the shape instead of on its boundary.

You control $k$ of the $n$ trees in the forest. You want to extend your power by gaining control of one more tree, anywhere in the forest. After you take the single tree that increases your power the most, what is the area of your new shape?

Input

The input is one test case. Your program may be run several times on different inputs.

The first line contains two 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 you control.

Each of the next $n$ lines contains two integers $x$ and $y$ ( $-10^9 \le x, y \le 10^9$ ), the position of one tree. The first $k$ trees in the list are the trees you control. No three trees are collinear. A tree you do not control may lie inside your shape.

Output

Print the largest area you can reach by taking control of one more tree, with exactly one digit after the decimal point. Every coordinate is an integer, so this area is always a multiple of $0.5$ .

Examples3

Example 1
Input
```
5 3
-5 -5
-5 5
5 -5
-4 6
5 5
```
Expected output
```
100.0
```
Example 2
Input
```
4 3
0 0
10 0
3 9
4 3
```
Expected output
```
45.0
```
Example 3
Input
```
4 3
0 0
3 0
0 2
2 3
```
Expected output
```
6.5
```