#P17530. [JAG 2026 Summer Camp #1] JAG City Marathon I
[JAG 2026 Summer Camp #1] JAG City Marathon I
题目描述
Just A Grid 城市(简称 JAG 城市)有 条水平道路和 条竖直道路。这些道路构成一个正方形网格。任意两条相邻的平行道路之间的距离均为 。水平道路从上到下编号为 到 ,竖直道路从左到右编号为 到 。我们将第 条水平道路与第 条竖直道路的交点记为 。
JAG 城市的道路上即将举行一场马拉松。为了让跑者经过城市中的更多地方,组织者设置了 个检查点。给定一个 的排列 。检查点位于 ()。
组织者希望比赛路线易于遵循。因此,马拉松路线必须满足以下所有条件:
- 路线是仅沿道路行进的闭合路线。
- 路线经过全部 条水平道路和全部 条竖直道路,并且在每条道路上行进的距离至少为 。
- 路线经过每个检查点,并在每个检查点处转弯。
- 路线恰好转弯 次。
路线允许自交,即使交叉发生在路线不转弯的交点处也可以。每次转弯时,路线从水平道路转入竖直道路,或从竖直道路转入水平道路。
若一条路线满足上述所有条件,则称其为合法路线。保证至少存在一条合法路线。在所有合法路线中,输出一条长度最大的路线。

图 E-1:合法与不合法的马拉松路线示例。图中从左到右的标签分别表示“合法但非最优”“最优”“不合法”“不合法”;Checkpoint 表示检查点。
图 E-1 展示了样例输入对应的四条路线。最左边的路线合法但非最优,长度为 。第二条路线最优,长度为 。虽然它在两个不转弯的交点处自交,但这样的交叉是允许的。第三条路线不合法,因为它经过了一个检查点,却没有在那里转弯。最右边的路线不合法,因为它的转弯次数超过了 。
输入格式
输入包含一组测试数据,格式如下:
N
P_1 P_2 ... P_N
第一行包含一个整数 (),表示每个方向的道路数量。
第二行包含 个互不相同的整数 (),构成排列 。
输出格式
设 为合法路线的最大可能长度。
输出 ,以及一条长度为 的合法路线的 个转弯交点。交点按照沿路线经过的顺序输出,格式如下:
L
X_1 Y_1
X_2 Y_2
...
X_{2N} Y_{2N}
对于每个 (),二元组 表示第 条水平道路与第 条竖直道路的交点,其中 。
若有多条长度为 的合法路线,可以输出其中任意一条。
你可以选择任意一个转弯交点作为 ,并沿路线的任意一个方向输出这些交点。
4
2 4 1 3
14
1 2
1 3
4 3
4 1
3 1
3 4
2 4
2 2