[SDCPC2023] Computational Geometry

**【题目描述】** 给定一个有 $n$ 个顶点的凸多边形 $P$，您需要选择 $P$ 的三个顶点，按逆时针顺序记为 $a$，$b$ 和 $c$。要求在 $b$ 沿逆时针方向到 $c$ 之间恰有 $k$ 条边（也就是说，$a$ 不是这 $k$ 条边的端点）。 考虑用线段 $ab$ 和 $ac$ 将 $P$ 割开。将由线段 $ab$，$ac$，以及 $b$ 和 $c$ 之间的 $k$ 条边围成的 $(k + 2)$ 边形记作 $Q$。 求 $Q$ 可能的最大面积。 注意，$ab$ 和 $ac$ 可以与 $P$ 的边重合。 **【输入格式】** 有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $k$（$3 \le n \le 10^5$，$1 \le k \le n-2$），表示凸多边形 $P$ 的顶点数和 $b$ 沿逆时针方向到 $c$ 之间的边数。 对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示凸多边形 $P$ 第 $i$ 个顶点的 $x$ 坐标和 $y$ 坐标。顶点按逆时针顺序给出。保证凸多边形的面积为正，且没有顶点会重合。可能存在三个顶点位于同一条直线上的情况。 保证所有数据 $n$ 之和不超过 $10^5$。 **【输出格式】** 每组数据输出一行一个实数表示 $Q$ 的最大可能面积。只要您的答案的相对误差或绝对误差小于$10^{-9}$ 即视为正确。 **【样例解释】** 对于第一组样例数据，$Q$ 就是整个三角形，面积为 $0.5$. 第二和第三组样例数据解释如下。  

Given a convex polygon $P$ with $n$ vertices, you need to choose three vertices of $P$, denoted as $a$, $b$ and $c$ in counter-clockwise order. There must be exactly $k$ edges from $b$ to $c$ in counter-clockwise order (that is to say, $a$ is not an endpoint of these $k$ edges). Consider cutting through $P$ with segment $ab$ and $ac$. Let $Q$ be the polygon consisting of $ab$, $ac$ and the $k$ edges between $b$ and $c$. It's easy to see that this polygon has $(k + 2)$ edges. Find the maximum possible area of $Q$. Note that $ab$ and $ac$ can overlap with edges of $P$.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($3 \le n \le 10^5$, $1 \le k \le n-2$) indicating the number of vertices of the convex polygon $P$ and the number of edges from $b$ to $c$ in counter-clockwise order. For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) indicating the $x$ and $y$ coordinate of the $i$-th vertex of the convex polygon $P$. Vertices are given in counter-clockwise order. It's guaranteed that the area of the convex polygon is positive, and there are no two vertices with the same coordinate. It's possible that three vertices lie on the same line. It's guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.

For each test case output one line containing one real number indicating the maximum possible area of $Q$. Your answer will be considered correct if its relative or absolute error is less than $10^{-9}$.

3
3 1
0 0
1 0
0 1
8 3
1 2
3 1
5 1
7 3
8 6
5 8
3 7
1 5
7 2
3 6
1 1
3 1
7 1
8 1
5 6
4 6

0.500000000000
26.500000000000
20.000000000000

For the first sample test case, $Q$ is the whole triangle. Its area is $0.5$. The second and third sample test case are shown below.