Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,0.5G}$。

Problem Description

You are given $N$ points on a 2D plane. Choose $K$ points to maximize the area of the convex hull of these $K$ points.

In addition, you must choose the two points with the minimum and maximum $x$ coordinates on the plane. It is guaranteed that there are no other points on the two lines parallel to the $y$ axis that pass through these two points, and the $y$ coordinates of these two points are $0$.

You only need to output the maximum area.

Input Format

The first line contains two positive integers $N, K$.

The next $N$ lines each contain two integers $x_i, y_i$, describing a point.

Output Format

Output one real number on a single line, representing the maximum convex hull area.

The output should not contain extra leading zeros or trailing zeros.

6 4
0 0
9 0
2 8
6 5
2 -7
8 -7

67.5

5 3
0 0
10 0
5 0
5 5
5 -5

25

8 5
0 0
15 0
2 -2
4 12
10 -14
6 -12
2 -10
13 10

238

Hint

• Explanation for Sample $1$: choose $(0, 0), (2, −7), (2, 8), (9, 0)$.
• Explanation for Sample $2$: choose $(0, 0), (10, 0), (5, −5)$.

You may also refer to the figure below.

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $3 \le K \le N \le 3\,000$；
• $|x_i|, |y_i| \le 10^9$；
• All given points are distinct；
• The points with the minimum and maximum $x$ coordinates are unique, and their corresponding $y$ coordinates are $0$。

Translated by ChatGPT 5