Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:64 MB

#345. PARALELOGRAMI

统计

题目描述

最近,一个叫 _Parallelograms_ 的游戏迅速在网络上流行。游戏一开始有$N$个点,每个点的坐标互不相同。每次操作你可以选择三个不共线的点$A,B,C$,然后,画出点$D$,使得四边形$ACBD$是以$AB$为对角线的平行四边形,然后把点$C$移动到点$D$。注意这样的点$D$有且仅有一个。

虽然在一开始所有点的坐标都互不相同,但是,你可以通过若干次操作使得某些点的坐标相同。与此同时,所有点的坐标的绝对值不能超过$10^9$。

现在,请你通过最多$2500$次操作,使得最终所有点都在第一象限,或者报告不存在操作方案。请注意,你并不需要求出操作次数最少的操作方案,你只需要求出操作次数不超过$2500$且满足题目要求的方案即可。

输入输出格式

输入格式

第一行输入一个整数$N$,表示点的个数。
随后$N$行,每行两个整数$X_i,Y_i$,分别表示第$i$个点的横坐标和纵坐标。

输出格式

如果无解,输出一行 -1

否则,第一行输出一个整数$M$,表示操作次数。
随后$M$行,每行三个整数$A,B,C$,表示一次操作中选择的三个点的编号。点$C$按照题目描述部分所述规则变换,而点$A,B$不做任何变换。

输入输出样例

输入样例 #1

3
0 0
4 0
3 -1

输出样例 #1

1
1 2 3

输入样例 #2

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

输出样例 #2

2
1 2 3
1 2 4

输入样例 #3

3
-1 -1
-2 -2
-3 -3

输出样例 #3

-1

说明/提示

【数据范围】

对于所有数据,$3\leqslant N\leqslant 400$,$-10\leqslant X_i,Y_i\leqslant 10$。