这是一个交互问题。
粉红士兵向你隐藏 $$$n$$$ ($$$3 \le n \le 1500$$$) 已修复 点 $$$(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$$$, 没有给你坐标。此外,已知没有两点具有相同的坐标,也没有三点共线。
你可以向主唱询问三个 不同 上面写着 索引 $$$i$$$、$$$j$$$、$$$k$$$。然后,他将用点 $$$(x_i,y_i)$$$、$$$(x_j,y_j)$$$、$$$(x_k,y_k)$$$ 绘制一个三角形,并做出以下响应:
- 如果至少有一个隐藏点位于三角形内部,则主唱会为您提供一个此类点的索引。请注意,如果有多个这样的点, 主唱可以任意选择其中之一.
- 否则,主唱将以 $$$0$$$ 响应。
此问题的目标是找到一个不包含任何其他隐藏点的三角形,例如图中的蓝色三角形。 最多使用 $$$\mathbf{75}$$$ 查询,您必须找到由其中三个点形成的任何三角形, 不包含 内部任何其他隐藏点。
请注意,主唱可能是 自适应 同时选择给你的点。换句话说,点的选择可以由各种因素来确定,包括但不限于点的方向和先前的查询。但请注意 点的顺序永远不会改变.
对于此问题,黑客已被禁用。您的解决方案将完全根据 $$$\mathbf{35}$$$ 输入文件(包括示例输入)进行判断。
互动
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个正整数 $$$n$$$ — 点数 ($$$3 \le n \le 1500$$$)。
之后,您可以在单独的行上输出以下内容来进行查询:
- "?我jk" ($$$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$$$。
如果要打印答案,可以在单独的行中输出以下内容:
- "!我jk" ($$$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{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
对于此问题,黑客已被禁用。您的解决方案将完全根据 $$$\mathbf{35}$$$ 输入文件(包括示例输入)进行判断。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 6 5 4 0 3
输出复制
? 1 2 3 ? 1 5 3 ? 2 5 6 ! 2 5 6 ! 1 2 3
注意
在第一个测试用例中,点为 $$$(3,0),(0,3),(5,2),(3,1),(2,2),(4,4)$$$。
三个查询对应的三角形如下。
可以看到$$$(0,3)$$$、$$$(2,2)$$$、$$$(4,4)$$$形成的三角形内部不包含任何其他隐藏点。因此,这是一个有效的答案。
请注意,交互示例仅显示有效的交互,并且 不一定是实际响应。例如,当您查询“时,Frontman 可能会返回 $$$4$$$”? 1 2 3“。然而,由于主唱不会改变点的顺序,因此对于同一查询,他永远不会以 $$$6$$$ 进行响应。
在第二个测试用例中,只有 $$$3$$$ 点。因此,我们知道由点组成的唯一三角形内部不包含任何其他隐藏点。