P16537 [THUPC 2026 Finals] Redrawing the Star Map

From the finals of the 2026 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2026). Resources such as the editorial can be found at https://github.com/dapingguo8/THUPC2026-final. > As the streaming-light decryption challenge came to a perfect end, the holographic light tree was fully lit up, and the grand 10th anniversary celebration quietly approached its finale. As the last part of the celebration, Little T and Little S invited everyone to a digital drawing board covered with a sky full of star maps. > > As time passed, the constellation lines drawn in the past had faded away, and the board returned to the appearance of only isolated stars scattered around. Little S handed out special star-map pens to everyone present, hoping that they could complete this star map again. To make the redrawn commemorative star map look as beautiful as possible, the structure must remain balanced when connecting the stars. > > Along with the gentle melody, people stepped forward one after another, hoping to light up as many constellations as possible in this sea of stars, and leave the most brilliant finale for this 10th anniversary evening party.

There are $n$ stars on the board, which can be considered as points on a 2D plane. The coordinates of the $i \ (1 \le i \le n)$-th star are $(x_i, y_i)$. It is known that all $x$-coordinates are pairwise distinct, and all $y$-coordinates are also pairwise distinct. Each time you draw a constellation, you need to choose three stars from these $n$ stars, and connect them pairwise to form a triangle. To reflect the beauty of balance, this triangle must satisfy a special boundary requirement: there exists a rectangle whose four sides are all parallel to the coordinate axes, such that the three vertices of the triangle all lie exactly on the boundary of this rectangle. Also, to keep the star map clear, the interior regions of all drawn triangles (excluding vertices and edges) must be pairwise non-intersecting. Please compute the maximum number of constellations that can be drawn successfully, and output one specific drawing plan.

This problem contains multiple test cases. The first line contains a positive integer $t\ (1\le t\le 2\times 10^4)$, indicating the number of test cases. For each test case, the first line contains a positive integer $n \ (3 \le n \le 2 \times 10 ^ 5)$. Then follow $n$ lines. The $i \ (1 \le i \le n)$-th line contains two integers $x_i, y_i \ (\lvert x_i \rvert, \lvert y_i \rvert \le 10 ^ 9)$, representing the coordinates of the $i$-th star. It is guaranteed that all $x_i$ are pairwise distinct and all $y_i$ are pairwise distinct.

For each test case, output a non-negative integer $m$ on the first line, representing the maximum number of constellations that can be drawn. Then output $m$ lines. Each line outputs three pairwise distinct positive integers $x, y, z \ (1 \le x, y, z \le n)$, indicating the three stars that form one constellation.

The illustration of the first test case in the sample is as follows. :::align{center}  ::: The illustration of the second test case in the sample is as follows. :::align{center}  ::: Translated by ChatGPT 5