← 返回题目列表

Codeforces · 1508/D

D. 交换通行证

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

根据篮球训练中的一个奇特事件,Akari 提出了以下竞技编程问题!

平面上有 $$$n$$$ 个点,其中没有三个点共线。第 $$$i$$$ 个点最初有一个标签 $$$a_i$$$,这样标签 $$$a_1, a_2, \dots, a_n$$$ 形成 $$$1, 2, \dots, n$$$ 的排列。

您可以通过以下操作修改标签:

1. 在 $$$1$$$ 和 $$$n$$$ 之间选择两个不同的整数 $$$i$$$ 和 $$$j$$$。
2、交换点$$$i$$$和$$$j$$$的标签,最后
3. 在点 $$$i$$$ 和 $$$j$$$ 之间绘制线段。

如果按顺序应用序列中的所有操作后,对于 $$$1$$$ 和 $$$n$$$ 之间的所有 $$$k$$$,第 $$$k$$$ 个点最终具有标签 $$$k$$$ ,并且绘制的线段在内部彼此不相交,则该操作序列是有效的。形式上,如果两个线段相交,那么它们必须在两个线段的公共端点处相交。

特别是,所有绘制的线段必须是不同的。

找到任何有效的操作序列,或者说不存在。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2000$$$) — 点数。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含三个整数 $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$, $$$1 \le a_i \le n$$$),表示第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i)$$$,最初的标签为 $$$a_i$$$。

保证所有点都是不同的,没有三个点共线,并且标签 $$$a_1, a_2, \dots, a_n$$$ 形成 $$$1, 2, \dots, n$$$ 的排列。

输出

如果无法执行有效的操作序列,则打印 $$$-1$$$。

否则,打印一个整数 $$$k$$$ ($$$0 \le k \le \frac{n(n - 1)}{2}$$$) — 要执行的操作数,后跟 $$$k$$$ 行,每行包含两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i\neq j$$$) — 为操作选择的点的索引。

请注意,您不需要最小化或最大化 $$$k$$$ 的值。

如果有多个可能的答案,您可以打印其中任何一个。

示例

输入 #1

5
-1 -2 2
3 0 5
1 3 4
4 -3 3
5 2 1

输出 #1

5
1 2
5 3
4 5
1 5
1 3

输入 #2

3
5 4 1
0 0 2
-3 -2 3

输出 #2

0

注意

以下动画展示了第一个示例测试用例。黑色数字代表点的索引,而方框中的橙色数字代表它们的标签。

在第二个测试用例中,所有标签都已处于正确位置,因此无需执行任何操作。