← 返回题目列表

Codeforces · 2074/E

E. 空三角形

中文机器翻译题面 查看原题

这是一个交互问题。

粉红士兵向你隐藏 $$$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$$$ 点。因此,我们知道由点组成的唯一三角形内部不包含任何其他隐藏点。