P11023 [COTS 2020] Kingdom Kraljevstvo

Translated from [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D1T1。$\texttt{1s,0.5G}$。

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.

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 one real number on a single line, representing the maximum convex hull area. The output should not contain extra leading zeros or trailing zeros.

#### - 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$。 | Subtask ID | $N \le$ | Score | | :--: | :--: | :--: | | $1$ | $20$ | $11$ | | $2$ | $100$ | $25$ | | $3$ | $500$ | $15$ | | $4$ | $3\,000$ | $49$ | Translated by ChatGPT 5