P8042 [COCI 2016/2017 #7] PARALELOGRAMI

Recently, a game called _Parallelograms_ has quickly become popular on the Internet. At the beginning of the game, there are $N$ points, and the coordinates of all points are **pairwise distinct**. In each operation, you can choose three **non-collinear** points $A,B,C$, and then draw a point $D$ such that the quadrilateral $ACBD$ is a parallelogram with $AB$ as a diagonal, and then move point $C$ to point $D$. Note that there is **exactly one** such point $D$. Although initially all points have distinct coordinates, you may make some points share the same coordinates after several operations. At the same time, the absolute values of all coordinates must not exceed $10^9$. Now, please use at most $2500$ operations to make all points end up in the first quadrant, or report that no valid sequence of operations exists. Note that **you do not need to find a sequence with the minimum number of operations**. You only need to output a sequence with no more than $2500$ operations that satisfies the requirements.

The first line contains an integer $N$, representing the number of points. The next $N$ lines each contain two integers $X_i,Y_i$, representing the $x$-coordinate and $y$-coordinate of the $i$-th point.

If there is no solution, output one line `-1`. Otherwise, the first line outputs an integer $M$, representing the number of operations. The next $M$ lines each contain three integers $A,B,C$, representing the indices of the three points chosen in one operation. Point $C$ is transformed according to the rule described in the Description section, while points $A,B$ are not changed.

**Constraints** For all testdata, $3\leqslant N\leqslant 400$, $-10\leqslant X_i,Y_i\leqslant 10$. **Source** This problem is from **_[COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST 7](https://hsin.hr/coci/archive/2016_2017/contest7_tasks.pdf) T5 PARALELOGRAMI_**. With the original testdata settings, the full score is $140$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Thanks to [mutton](https://www.luogu.com.cn/user/137367) for providing the [SPJ](https://www.luogu.com.cn/paste/ck8tv23j) for this problem. If you have hack data, please send a private message to mutton. Translated by ChatGPT 5