ICPC PACNW 2016 E - Enclosure

View as PDF

Submit solution

Points: 30
Time limit: 1.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 kk out of nn 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?


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

Next follow nn lines each with two space-separated integers x_ix_i and y_iy_i (|x_i|,|y_i| \le 10^9)(|x_i|,|y_i| \le 10^9) specifying the locations of the nn trees. You control the first kk trees given in the list; the other n-kn-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.


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

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


There are no comments at the moment.