CF2074E.Empty Triangle

这是一道交互题。

粉色士兵们向你隐藏了 $n$ 个（$3 \le n \le 1500$）固定点 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$，其坐标未给出。已知任意两点坐标不同，且任意三点不共线。

你可以向主持人（Frontman）询问三个不同的下标 $i$、$j$、$k$。随后，主持人会绘制由点 $(x_i, y_i)$、$(x_j, y_j)$、$(x_k, y_k)$ 构成的三角形，并按以下规则回应：

• 若至少有一个隐藏点位于三角形内部，主持人会返回其中一个这样的点的下标。注意，若有多个这样的点，主持人可以任意选择其中一个返回。
• 否则，主持人返回 $0$。

你的目标是找到一个不包含其他隐藏点的三角形（如图中蓝色三角形所示）。你最多可以使用 $\mathbf{75}$ 次询问，找到由三个点构成的、内部不含其他隐藏点的任意三角形。

注意：主持人可能在选择返回的点时具有自适应性。换言之，返回点的选择可能受到多种因素影响（包括但不限于点的排列和之前的询问）。但需注意，点的序列永远不会被改变。

本题禁用 hack。你的解法将在恰好 $\mathbf{35}$ 个输入文件（包括示例输入）上进行评测。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 20$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个正整数 $n$ —— 点的数量（$3 \le n \le 1500$）。

之后，你可以在单独一行输出以下内容进行询问：

• "? i j k"（$1 \le i,j,k \le n$，$i \ne j$，$i \ne k$，$j \ne k$）：询问由 $(x_i, y_i)$、$(x_j, y_j)$、$(x_k, y_k)$ 构成的三角形。

随后，交互器会在新的一行返回一个整数：

• 若你的询问无效或询问次数超过 $\mathbf{75}$ 次，交互器返回 $-1$；
• 若存在下标 $p$（$1 \le p \le n$）使得点 $(x_p, y_p)$ 位于三角形内部，则返回任意一个这样的下标 $p$；
• 否则，交互器返回 $0$。

若你想提交答案，可以在单独一行输出以下内容：

• "! i j k"（$1 \le i,j,k \le n$，$i \ne j$，$i \ne k$，$j \ne k$）：表示由 $(x_i, y_i)$、$(x_j, y_j)$、$(x_k, y_k)$ 构成的三角形内部不含其他隐藏点。

随后，以下交互会发生：

• 若答案无效或三角形包含其他隐藏点，交互器返回 $-1$；
• 若答案正确且仍有未处理的测试用例，你将获得下一个测试用例的 $n$ 值；
• 否则，表示所有测试用例已正确解决，你的程序可正常终止。

注意：提交答案不计入询问次数。

注意：交互器可能在选择返回的点时具有自适应性。换言之，返回点的选择可能受到多种因素影响（包括但不限于点的排列和之前的询问）。但需注意，点的序列永远不会被改变。

每次输出询问后，请勿忘记换行并刷新$^{\text{∗}}$输出缓冲区。否则，你将收到 Idleness limit exceeded 的判定结果。

若在交互过程中读取到 $-1$ 而非有效数据，你的程序必须立即终止。这意味着你的程序将因无效询问或其他错误被判定为 Wrong answer。未能终止可能导致任意判定结果，因为程序会继续从已关闭的流中读取数据。

Hacks

本题禁用 hack。你的解法将在恰好 $\mathbf{35}$ 个输入文件（包括示例输入）上进行评测。

$^{\text{∗}}$ 刷新缓冲区的方法：

• C++ 使用 fflush(stdout) 或 cout.flush()；
• Python 使用 sys.stdout.flush()；
• 其他语言请参考文档。

第一个测试用例中的点为 $(3,0),(0,3),(5,2),(3,1),(2,2),(4,4)$。

三次询问对应的三角形如下：

可以看到，由 $(0,3)$、$(2,2)$、$(4,4)$ 构成的三角形内部不含其他隐藏点，因此是一个有效答案。

注意：交互示例仅展示合法的交互流程，不一定是实际响应。例如，当查询 "? 1 2 3" 时，主持人可能返回 $4$。但由于主持人不会改变点的序列，因此不会对同一查询返回 $6$。

第二个测试用例中仅有 $3$ 个点。因此，由这三点构成的唯一三角形内部不含其他隐藏点。

翻译由 DeepSeek R1 完成