← 返回题目列表

Codeforces · 1045/E

E. 古代文明

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

在一颗新发现的行星(我们用飞机建模)的表面上,探险家在不同地点发现了两种不同文明的遗迹。他们希望更多地了解这些文明,并探索在一些地点之间修建道路所需的区域。但与往常一样,有一些限制:

1.同一文明的每两个地点由一条独特的道路连接
2.来自不同文明的两个地点之间不能有道路(探索者不想意外地混合他们当前正在探索的文明)
3.道路必须是直线段
4. 由于交叉路口的建设成本很高,因此他们不希望任何两条道路相交(也就是说,任何两条道路的公共点可能只在某些位置)

显然,所有位置都是平面上的不同点,但探险家发现了一个更有趣的信息,可能会对您有所帮助 - 没有三个位置位于同一条线上!

帮助探索者找到问题的解决方案,或者报告这是不可能的。

输入

在第一行中,整数 $$$n$$$ $$$(1 \leq n \leq 10^3)​​$$$ - 发现的位置数。

在接下来的 $$$n$$$ 行中,三个整数 $$$x, y, c$$$ $$$(0 \leq x, y \leq 10^4, c \in \{0, 1\})$$$ - 其所属文明的位置和编号。

输出

在第一行打印应修建的道路数量。

在下面的行中,打印应与道路连接的所有位置对(基于 $$$0$$$ 的索引)。

如果不可能修建满足所有限制的道路,请打印“不可能”。您不应打印引号。

示例

输入 #1

5
0 0 1
1 0 0
0 1 0
1 1 1
3 2 0

输出 #1

3
1 4
4 2
3 0