这是官方题解的 AI 翻译，使用了 GPT-5.5 Thinking 模型。

题目要求我们构造一个对点集凸包的划分。

对于不带最大化的子任务，只需要求出凸包即可；对于带最大化的子任务，则需要构造整个点集的一个三角剖分。

询问能做到什么

注意，这个询问本质上可以支持下面三类判断。

1. 给定点 $A,B,C,D$，比较 $\operatorname{dist}(C,AB)$ 和 $\operatorname{dist}(D,AB)$ 谁更大。
   只需要比较 $S(ABC)$ 和 $S(ABD)$ 即可。

2. 给定点 $A,B,C,D$，判断点 $D$ 是否在三角形 $ABC$ 内。
   只需要检查是否有
   $S(ABC)=S(ABD)+S(ACD)+S(BCD)$。

3. 给定点 $A,B,C,D$，判断线段 $AB$ 和 $CD$ 是否相交。
   只需要检查是否有
   $S(ABC)+S(ABD)=S(ACD)+S(BCD)$。
   这里恰好用到了 $ABCD$ 不是梯形这一条件；如果是梯形，上式成立时线段也未必真的相交。

前两个子任务：$n=4$

对于前两个子任务，直接分类讨论即可。

做法是：依次检查每个点是否落在其余三个点构成的三角形内部。

• 如果存在这样的点，那么三角剖分里会有 $3$ 个三角形。
• 否则，这四个点构成一个凸四边形。此时把它划成 $2$ 个三角形即可。比如可以检查哪两条线段相交，它们就是四边形的两条对角线。

一个重要观察：如何找凸包上的点

有一个很关键的结论：可以在 $n-2$ 次询问内找到一个凸包上的点。

做法如下：

先任取两个点，比如 $A_0,A_1$。然后在其余所有点里，找到使得 $S(A_0A_1A_i)$ 最大的那个点 $A_i$。

那么 $A_i$ 一定在凸包上。原因很简单：它到直线 $A_0A_1$ 的距离最大，也就是 $\operatorname{dist}(A_i,A_0A_1)$ 最大。

于是，我们可以在 $\le 3n$ 次询问内找到三个凸包上的点。
在第 $3,4$ 组数据中，这三个点其实已经构成了整个凸包。

对于第 $4$ 组里“需要在一个三角形内继续做三角剖分”的部分，可以这样处理：

在三角形内部随机选一个点。它会把原三角形划成 $3$ 个更小的三角形。接着，对剩余每个点，用第二类询问判断它属于哪一个小三角形，然后递归处理即可。

由于三角形内部的点是随机的，这个过程期望需要 $O(n\log n)$ 次询问。

更进一步：先把点分到两侧

接下来考虑更大的数据范围。

先找到两个在凸包上的点 $A_0,A_1$（不妨认为它们的编号就是这样），这一步需要 $\le 2n$ 次询问。

接着，把其余所有点按直线 $A_0A_1$ 分到两个不同半平面里。做法是：

取第三个点 $A_2$，然后对每个其余点 $A_i$，判断线段 $A_0A_1$ 和 $A_2A_i$ 是否相交。

这一部分还需要额外 $\le n$ 次询问。

之后，两侧可以独立求解。因此，下文不妨假设：所有点都在直线 $A_0A_1$ 的同一侧。

然后，把这些点按照它们到直线 $A_0A_1$ 的距离从小到大排序。
这一步需要 $\le n\log_2 n$ 次询问。

第五组的做法

在第 $5$ 组里，我们可以取距离直线 $A_0A_1$ 最远的点 $A_i$，再把剩下所有点按照它们位于直线 $A_0A_i$ 的哪一侧分开，这一步仍然只需要 $\le n$ 次询问。

这时，每一部分里的点都会呈现出单调性，而且我们已经知道它们按“高度”的顺序。于是答案总共可以在

$$\le n\log_2 n+4n$$

次询问内求出，完全可以通过。

满分做法：按“到直线的距离”做 Graham 扫描

满分解法的核心思路是：

在按“到直线 $A_0A_1$ 的距离”排序之后，套一个类似 Graham 扫描的过程。
虽然这里的排序不是按极角，而是按到一条基准直线的距离，但仍然可以维护凸包；更妙的是，在维护的同时还可以顺便构造三角剖分。

设这些点按到 $A_0A_1$ 的距离递增排序后为

$A_2,A_3,\dots,A_{n-1}$。

假设当前已经处理了前缀 $A_2,A_3,\dots,A_{i-1}$，那么维护如下状态：

• 点集 $A_0,A_1,A_2,\dots,A_{i-1}$ 的凸包，被拆成两条链：
  • 左链；
  • 右链。
• 同时已经构造出了这个凸包的一个三角剖分。

:::align{center} :::

例如原文图中的那个例子里，$i=11$。
左链是 $[A_0,A_4,A_7,A_8,A_{10}]$，右链是 $[A_1,A_5,A_9,A_{10}]$，现在要加入的点是 $A_{11}$。

初始化

初始化时只有点 $A_2$。

• 左链设为 $[A_0,A_2]$；
• 右链设为 $[A_1,A_2]$；
• 三角剖分里只有一个三角形 $A_0A_1A_2$。

如何加入新点 $A_i$

关键在于：要把 $A_i$ 分别加入左链和右链。

先看左链。假设左链当前为

$$[A_{l_0},A_{l_1},\dots,A_{l_k}]$$

其中 $l_0=0,\ l_k=i-1$。

和普通 Graham 扫描一样，我们需要删掉链尾的一段后缀，然后把 $A_i$ 接到末尾。

设当前正在检查链尾最后两个点 $A_{l_j}, A_{l_{j+1}}$。
如果满足

$$\overrightarrow{A_{l_j}A_{l_{j+1}}}\times\overrightarrow{A_{l_{j+1}}A_i}>0$$

那么就要删掉最后一个点 $A_{l_{j+1}}$。

而这个条件其实等价于：线段 $A_{l_j}A_i$ 与线段 $A_{l_{j+1}}A_1$ 不相交。
而线段相交正好可以用第三类询问判断出来。

因此，我们就能不断做这样的检查，把应删的那段后缀全部弹掉。

:::align{center} :::

原文图里的操作过程是：

• 检查 $A_8A_{11}$ 和 $A_{10}A_1$ 是否相交：不相交，所以删掉 $A_{10}$；
• 检查 $A_7A_{11}$ 和 $A_8A_1$ 是否相交：不相交，所以删掉 $A_8$；
• 检查 $A_4A_{11}$ 和 $A_7A_1$ 是否相交：相交，于是停止，并把 $A_{11}$ 接到链尾。

同时维护三角剖分

不仅如此，每当我们从链尾删掉一个点 $A_{l_{j+1}}$ 时，就把三角形

$A_{l_j}A_{l_{j+1}}A_i$

加入到答案的三角剖分里。

这样加入的这些三角形，恰好覆盖了从点 $A_i$ 向旧链作切线后，中间围出来的那一块区域。

:::align{center} :::

例如图中的左链更新时，就会向三角剖分里加入两个三角形：

• $A_8A_{10}A_{11}$；
• $A_7A_8A_{11}$。

右链同理做一遍即可，只不过判断时把上面的 $A_1$ 全部换成 $A_0$。

复杂度分析

这样一来，我们就同时得到了：

• 凸包；
• 凸包内部的三角剖分。

对于一条链而言，这个过程最多只需要 $\le 2n$ 次询问，因为每个点至多进栈一次、出栈一次。

所以两条链总共是 $\le 4n$ 次询问。

再加上最开始的排序和分类，总复杂度为

$$\le n\log_2 n+7n$$

如果对归并排序里的常数再仔细估一估，可以证明当 $n\le 10^4$ 时，这个做法是能卡进 $20n$ 次询问限制里的。

另外，排序部分还能再省一点：
如果改成把下标一个个插入当前有序序列，每次用二分查找位置，那么询问次数可以做到

$$\sum_{i=1}^{n}\lceil \log_2 i \rceil$$

这样常数会更漂亮一些。