P13502 [OOI 2024] Draw Polygon Lines

**这是一个交互题。** 给定 $n$ 个平面上的点 $A_i = (x_i, y_i)$。已知所有 $x_i$ 互不相同，所有 $y_i$ 也互不相同。 你的任务是将这 $n$ 个点连接成一条折线。 折线由一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$ 决定。折线由 $n-1$ 条线段组成，第 $1$ 条线段连接 $A_{p_1}$ 和 $A_{p_2}$，第 $2$ 条线段连接 $A_{p_2}$ 和 $A_{p_3}$，依此类推，最后一条线段连接 $A_{p_{n-1}}$ 和 $A_{p_n}$。注意，线段之间可以相交。 折线的**锐度**（sharpness）定义为满足 $2 \leq i \leq n-1$ 且 $\angle A_{p_{i-1}} A_{p_i} A_{p_{i+1}}$ 为锐角（即严格小于 $90^\circ$）的 $i$ 的数量。 你需要解决以下四个任务： - 求一条锐度最大的折线（即锐度尽可能大）。 - 给定整数 $c$，求一条锐度不超过 $c$ 的折线。 - 给定整数 $c$， 有 $q$ 个询问，每次给定一个整数 $k_i$（$c \leq k_i \leq n-c$）。对于第 $i$ 个询问，你需要构造一条锐度恰好为 $k_i$ 的折线。 - 给定整数 $c$， 对于每个 $k$ 从 $c$ 到 $n-c$，都要构造一条锐度恰好为 $k$ 的折线 $p^{(k)}$，并输出 $n-2c+1$ 个数 $\text{hash}\left(p^{(c)}\right), \text{hash}\left(p^{(c+1)}\right), \ldots, \text{hash}\left(p^{(n-c)}\right)$，其中 $$\text{hash}(p) = \left( \sum\limits_{i=1}^n p_i b^{i-1} \right) \bmod m$$ 这是排列 $p$ 的多项式哈希，参数 $b = 10^6 + 3$，$m = 10^9 + 7$。 然后有 $q$ 个询问，每次给定一个整数 $k_i$（$c \leq k_i \leq n-c$），你需要输出锐度恰好为 $k_i$ 的折线 $p^{(k_i)}$。会检查该折线的锐度是否为 $k_i$ 且哈希值是否等于之前输出的 $\text{hash}(p^{(k_i)})$。 注意这些询问会在你输出哈希值后出现。 保证在给定约束下，总有解存在。 ### 交互协议 第一行输入两个整数 $\text{task}$、$\text{group}$（$1 \leq \text{task} \leq 4$，$0 \leq \text{group} \leq 21$），表示本次测试要解决的任务编号和测试组编号。 第二行输入一个整数 $n$（$3 \leq n \leq 80\,000$），表示点的数量。 接下来 $n$ 行，每行两个整数 $x_i, y_i$（$|x_i|, |y_i| \leq 10^9$），表示一个点的坐标。保证所有 $x_i$ 互不相同，所有 $y_i$ 互不相同。 若 $\text{task} = 1$，输入到此结束，你需要输出一组锐度最大的排列。交互结束。 若 $\text{task} \neq 1$，则下一行输入一个整数 $c$（$2 \leq c \leq \frac{n}{2}$）。 若 $\text{task} = 2$，输入到此结束，你需要输出一组锐度不超过 $c$ 的排列。交互结束。 若 $\text{task} = 4$，你需要输出 $n-2c+1$ 个整数 $\text{hash}\left(p^{(c)}\right), \text{hash}\left(p^{(c+1)}\right), \ldots, \text{hash}\left(p^{(n-c)}\right)$，其中 $0 \leq \text{hash}\left(p^{(i)}\right) < 10^9 + 7$。注意如果 $\text{task} = 3$，则不需要输出哈希。 只有当 $\text{task} = 3$ 或 $\text{task} = 4$ 时，才会有进一步交互。 下一行输入一个整数 $q$（$1 \leq q \leq 50$），表示询问数量。 接下来 $q$ 行，每行一个整数 $k_i$（$c \leq k_i \leq n-c$）。对于每次询问，你需要在一行输出一个排列，要求该排列的锐度恰好为 $k_i$。若 $\text{task} = 4$，还需保证该排列的哈希值与之前输出的 $\text{hash}(p^{(k_i)})$ 相同。 **本题为交互题，每输出一行后不要忘记输出换行并刷新输出缓冲区。**

无

无

### 说明 所有图中，锐角用双圆弧表示，非锐角用单圆弧表示。  在第一个样例中，所有角都是锐角，因此折线的最大锐度为 $2$。 在第二个样例中，锐度为 $1$，满足 $\leq 2$。   在第三个样例中，折线的锐度分别为 $2$、$3$、$4$。  在第四个样例中，分别构造了锐度为 $2$ 和 $3$ 的折线，哈希值与之前输出的相同。 ### 计分方式 本题共二十一组测试。只有通过该组及其所有依赖组的所有测试，才能获得该组的分数。 | 组别 | 分值 | task | $n$ | $c$ | 额外约束 | 依赖组 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 0 | 0 | - | - | - | - | - | 样例。 | | 1 | 8 | 1 | $n \leq 20000$ | - | $x_i < x_{i+1}, y_i < y_{i+1}$ | - | | | 2 | 6 | 1 | $n \leq 10$ | - | 随机点 | - | | | 3 | 5 | 1 | $n \leq 1000$ | - | 随机点 | 2 | | | 4 | 5 | 1 | $n \leq 20000$ | - | 随机点 | 2 - 3 | | | 5 | 6 | 1 | $n \leq 20000$ | - | - | 1 - 4 | | | 6 | 17 | 2 | $n = 80000$ | $c = 800$ | - | - | | | 7 | 7 | 3 | $n = 80000$ | $c = 800$ | $x_i < x_{i+1}, y_i < y_{i+1}$ | - | | | 8 | 4 | 3 | $n = 50$ | $c = 25$ | 随机点 | - | | | 9 | 4 | 3 | $n = 200$ | $c = 80$ | 随机点 | - | | | 10 | 4 | 3 | $n = 1000$ | $c = 300$ | 随机点 | - | | | 11 | 3 | 3 | $n = 5000$ | $c = 600$ | 随机点 | - | | | 12 | 3 | 3 | $n = 80000$ | $c = 35000$ | 随机点 | - | | | 13 | 3 | 3 | $n = 80000$ | $c = 5000$ | 随机点 | 12 | | | 14 | 3 | 3 | $n = 80000$ | $c = 2000$ | - | 12 - 13 | | | 15 | 2 | 3 | $n = 80000$ | $c = 800$ | - | 7, 12 - 14 | | | 16 | 6 | 4 | $n = 80000$ | $c = 800$ | $x_i < x_{i+1}, y_i < y_{i+1}$ | - | | | 17 | 3 | 4 | $n = 5000$ | $c = 600$ | 随机点 | - | | | 18 | 3 | 4 | $n = 80000$ | $c = 35000$ | 随机点 | - | | | 19 | 3 | 4 | $n = 80000$ | $c = 5000$ | 随机点 | 18 | | | 20 | 3 | 4 | $n = 80000$ | $c = 2000$ | - | 18 - 19 | | | 21 | 2 | 4 | $n = 80000$ | $c = 800$ | - | 16, 18 - 20 | | 在说明为“随机点”的组别中，所有点的坐标 $x_i, y_i$ 均等概率随机生成于区间 $[-10^9, 10^9]$。 翻译由 ChatGPT-4.1 完成。