QOJ.ac

QOJ

时间限制: 2.0 s 内存限制: 512 MB 总分: 100 交互

#12322. 外星人入侵

统计

这是一个交互式问题。

最近,来自 Nibiru 星球(也称为 Not-Taking-It)的外星人决定入侵地球。作为 Nibiru 特种部队总部的指挥官,你正计划将第一批宇宙飞船降落在地球上最和平的国家——Byteland。

你知道 Byteland 的领土形状是一个平面上的 $n$ 边形(是的,Byteland 不大,所以我们可以将 Byteland 周围的表面视为平面的一部分)。该多边形的每个顶点代表一个城镇,每条边代表 Byteland 边界的一部分。当然,边界不能自交,且多边形的任意两条边仅在它们相邻时才有一个公共点(此时恰好有一个公共点)。

你的任务是求出 Byteland 的精确面积,以便计算部署在那里的宇宙飞船数量。然而,你并不知道 Byteland 的确切形状,因为发现它需要花费太长时间。幸运的是,Nibiru 情报局已经在 Byteland 的 $n$ 个城镇中各安插了一名间谍。每名间谍都有一盏巨大的信号灯。你还知道,间谍的编号为 $1$ 到 $n$,编号相邻的间谍(即编号差为 $1$ 或 $n-1$)位于由边界直接相连的城镇中。

你可以执行以下特殊操作:首先,你告诉每名间谍将他们的灯打开或关闭。然后,你派一名宇航员前往地球,她会看到所有亮着的灯,并告诉你包含这些灯的最小凸集的面积(换句话说,这些灯的凸包面积)。由于在太空中难以保持方向感,宇航员无法提供关于城镇位置的其他任何信息。

注意,如果你执行特殊操作的次数超过 $\frac{n(n-1)}{2}$ 次,Byteland 警方就会察觉到异常,入侵将失败。请在不引起过多注意的情况下求出 Byteland 的精确面积!

交互

首先,你将获得一个整数 $n$ ($3 \le n \le 200$),即代表 Byteland 的多边形的顶点数。

然后,你可以执行最多 $\frac{n(n-1)}{2}$ 次特殊操作。描述特殊操作的查询应包含两行: ? $k$ $a_1$ $a_2$ $\dots$ $a_k$

其中 $k$ ($3 \le k \le n$) 是需要打开灯的间谍数量,$a_1, \dots, a_k$ ($1 \le a_i \le n, a_i \neq a_j$ 当 $i \neq j$) 是这些间谍所在城镇的编号。所有其他城镇的间谍将关闭他们的灯。

执行查询后,你应该从输入中读取一行,其中包含一个非负数:亮灯的凸包面积(单位为平方米)。

当你认为你知道 Byteland 的面积 $x$ 时,打印 ! $x$

在单行上。打印答案不计入特殊操作次数。答案必须精确,不允许有任何误差,也不允许有前导零。之后,你的程序应正常终止。

请记住,在进行查询或打印答案后,请换行并刷新输出缓冲区。

保证多边形在程序执行期间不会改变,且多边形的面积严格大于零。此外,保证存在一个包含 Byteland 的平面笛卡尔坐标系,使得多边形所有顶点的坐标(以米为单位)均为 $[-10^9, 10^9]$ 范围内的整数。

样例

输入 1

3
0.5

输出 1

? 3
1 2 3
! 0.5

说明

对于样例测试,Byteland 的城镇位于某个笛卡尔坐标系下的点 $(0, 0)$、$(0, 1)$ 和 $(1, 0)$。

注意,样例输入和输出中的空行仅为清晰起见而打印,实际并不存在。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.