CF1254C Point Ordering

这是一个交互题。 Khanh 在笛卡尔平面上有 $n$ 个点，记为 $a_1, a_2, \ldots, a_n$。所有点的坐标都是 $-10^9$ 到 $10^9$ 之间的整数，且任意三点不共线。他声称这些点是一个凸多边形的顶点。换句话说，存在一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$，使得多边形 $a_{p_1} a_{p_2} \ldots a_{p_n}$ 是凸的，并且顶点按照逆时针顺序排列。 Khanh 会告诉你 $n$，但不会告诉你这些点的坐标。你的任务是通过多次询问猜出上述排列。在每次询问中，你需要给出 $4$ 个整数 $t$、$i$、$j$、$k$，其中 $t=1$ 或 $t=2$，$i$、$j$、$k$ 是 $1$ 到 $n$ 之间互不相同的三个下标。Khanh 会告诉你： - 如果 $t=1$，则返回三角形 $a_i a_j a_k$ 的面积乘以 $2$。 - 如果 $t=2$，则返回向量 $\overrightarrow{a_i a_j}$ 和 $\overrightarrow{a_i a_k}$ 的叉积的符号。 回忆一下，向量 $\overrightarrow{a} = (x_a, y_a)$ 和向量 $\overrightarrow{b} = (x_b, y_b)$ 的叉积为 $x_a \cdot y_b - x_b \cdot y_a$。一个数的符号为 $1$（如果它为正），否则为 $-1$。可以保证上述询问得到的叉积不为 $0$。 你最多可以询问 $3 \cdot n$ 次。 请注意，Khanh 固定了点的坐标，在回答你的询问时不会改变。你不需要猜出坐标。在你的排列 $a_{p_1} a_{p_2} \ldots a_{p_n}$ 中，$p_1$ 必须等于 $1$，并且顶点下标应按逆时针顺序排列。

你首先读入一个整数 $n$（$3 \leq n \leq 1000$）——顶点数。 每次询问时，输出 $4$ 个整数 $t$、$i$、$j$、$k$（$1 \leq t \leq 2$，$1 \leq i, j, k \leq n$），其中 $i$、$j$、$k$ 互不相同，单独一行。 然后读入一个整数，表示本次询问的答案，如上所述。可以保证答案总是整数。 当你确定排列后，输出一个数字 $0$，然后在同一行输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$。 每次输出后不要忘记换行并刷新输出缓冲区，否则会导致“Idleness limit exceeded”。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 Hack 时使用如下格式： 第一行包含一个整数 $n$（$3 \leq n \leq 1000$）——顶点数。 接下来 $n$ 行，每行两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示点 $a_i$ 的坐标。

见输入格式说明。

下图展示了样例中的隐藏多边形：  样例交互如下： - 选手读入 $n=6$。 - 选手询问 $t=1$，$i=1$，$j=4$，$k=6$。 - 测评机回答 $15$。三角形 $A_1A_4A_6$ 的面积为 $7.5$，注意答案是面积的两倍。 - 选手询问 $t=2$，$i=1$，$j=5$，$k=6$。 - 测评机回答 $-1$。$\overrightarrow{A_1A_5}=(2,2)$，$\overrightarrow{A_1A_6}=(4,1)$，叉积为 $-2$，其符号为 $-1$。 - 选手询问 $t=2$，$i=2$，$j=1$，$k=4$。 - 测评机回答 $1$。$\overrightarrow{A_2A_1}=(-5,2)$，$\overrightarrow{A_2A_4}=(-2,-1)$，叉积为 $1$，其符号为 $1$。 - 选手输出排列 $(1, 3, 4, 2, 6, 5)$。 由 ChatGPT 4.1 翻译