P5571 [CmdOI2019] Towers and Crystals

**Warm reminder: Please pay attention to the impact of constant factors on program efficiency + the special memory limit of this problem.** In the Kingdom of Geometry, there stand $n$ ancient towers. Legend says they are the guardians of this pure land. As geometry develops rapidly day by day, the kingdom’s prosperity attracts a terror from the depths of blazing flames: the moving point $P$. Before the hero Descartes, who can tame the “moving-point dragon,” appears, the lord of the Kingdom of Geometry decides to hold the line in the field of static geometry.

He obtained three “wisdom crystals” of static geometry (of course, they contain god-level math problems), and he can place them into the towers. Three towers with crystals placed can protect the interior of the triangle they form from invasion. However, if the area of the triangle formed by the crystals is too large, the defense line will be very easy to break. If the area of the triangle is too small, the geometric energy generated inside will not be enough to keep the crystals running. After several days of calculation, the lord believes that among the $\binom{n}{3}$ possible choices, the plan with the $k$-th **smallest** area is the most suitable. (The triangle area can be $0$.) He is still not confident about this result, so he asks you—who can crush countless geometry problems with one hand—to help him compute the exact value of this area.

The first line contains two integers $n,k$, with the meanings as described in the statement. The next $n$ lines: the $i$-th line contains two numbers $x_i,y_i$, representing the coordinates of tower $i$.

Output **twice** the area corresponding to the plan with the $k$-th **smallest** area. It is easy to prove that this must be an integer.

| subtask ID | 　n　 | Notes | Score | Time Limit | | :--: | :--: | :--: | :--: | :--: | | 1 | 200 | - | 15 | 1S | | 2 | 500 | $k\leq10$ | 20 | 1S | | 3 | 500 | $k\leq10000$ | 15 | 1S | | 4 | 800 | - | 50 | 2S | Constraints: $1\leq x_i,y_i \leq 10^6$, all coordinates are positive integers, and no two towers share the same coordinates. **Sample explanation:**  Translated by ChatGPT 5