P9397 "DBOI" Round 1 DTTM

Zhang Zeyu and Mu Zhicheng sit on the rooftop, looking at the star-filled sky. In their world, connecting stars is a popular activity. They give it a romantic meaning: if you cannot connect them all, then the one remaining star is the person beside you; if you can connect them all, then both you and the person beside you are stars.

There are $n$ stars in the sky. The $i$-th star is located at coordinates $(x_i, y_i)$. You need to connect the stars to satisfy Zhang Zeyu's requirements below: - Each star is an endpoint of exactly one line segment, and all segments do not intersect each other (including at endpoints). - The sum of $|x_l - x_r|$ over all segments, where $x_l$ and $x_r$ are the $x$-coordinates of the left and right endpoints, is minimized. However, Zhang Zeyu is a bit slow and does not know how to connect them. Mu Zhicheng knows you are the smartest person on Earth, so he gives you the coordinates of the $n$ stars. You need to output a connection plan or report that there is no solution.

The first line contains $n$, the number of stars. Starting from the second line, there are $n$ lines, each with two integers. Line $i+1$ gives the coordinates $(x_i, y_i)$ of the $i$-th star.

On the first line, output the minimum possible value of the sum of $|x_l - x_r|$ over all segments. Then, on each following line, output two indices, indicating the pair of stars connected by each segment to achieve the minimum value. If there are multiple valid connection plans, output any one of them. If there is no solution, output $-1$ on the first line.

The solution for Sample 1 is shown in the figure:  The solution for Sample 2 is shown in the figure:  **This problem uses bundled testdata and subtask dependencies.** | $\rm Subtask$ | $n\leqslant$ | $(x,y)$ | Special Property | Score | Subtask Dependencies | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $0\leqslant x,y\leqslant 20$ | None | $10$ | None | | $2$ | $10^3$ | $0\leqslant x,y\leqslant10^3$ | None | $15$ | $1$ | | $3$ | $10^3$ | $0\leqslant x,y\leqslant10^9$ | None | $15$ | $1,2$ | | $4$ | $5\times10^5$ | $-10^9\leqslant x,y\leqslant10^9$ | $A$ | $5$ | None | | $5$ | $5\times10^5$ | $-10^3\leqslant x,y\leqslant10^3$ | None | $20$ | $1,2$ | | $6$ | $5\times10^5$ | $-10^9\leqslant x,y\leqslant10^9$ | None | $35$ | $1,2,3,4,5$ | Special property $A$: all $x_i$ are equal. Constraints: For $100\%$ of the testdata, $1\leqslant n\leqslant 5\times 10^5$, $0\leqslant |x|,|y|\leqslant 10^9$, and for any $i\ne j$, $(x_i, y_i)\neq (x_j, y_j)$. Translated by ChatGPT 5