ICPC PACNW 2016 E - Enclosure

View as PDF

Submit solution

Points: 30
Time limit: 2.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Java, Python

In the Dark Forest, the territory you control is defined by the smallest convex polygon that contains all trees you control. Your power is defined by the area of the territory you control.

You currently control k out of n trees in the Dark Forest. What is the highest power you can achieve by gaining control over a single additional tree somewhere in the forest?

Input

The first line of input consists of two space-separated integers n and k\ (3 \leq k < n \leq 100\ 000).

Next follow n lines each with two space-separated integers x_i and y_i\ (|x_i|,|y_i| \leq 10^9) specifying the locations of the n trees. You control the first k trees given in the list; the other n-k trees do not belong to you. (Note that some of these may still be inside your territory.)

It is guaranteed that no three trees have collinear locations.

Output

Print, on a single line, the maximum power you can achieve by gaining control over a single additional tree. The output should be rounded and displayed to exactly one decimal place.

Sample Input

5 3
-5 -5
-5 5
5 -5
-4 6
5 5

Sample Output

100.0
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.