Swap Pass
Contest: Codeforces Round 715 (Div. 1)
Difficulty rating: 3000
Tags: constructive algorithms, geometry, sortings

Based on a peculiar incident at basketball practice, Akari came up with the following competitive programming problem!

You are given $$$n$$$ points on the plane, no three of which are collinear. The $$$i$$$-th point initially has a label $$$a_i$$$, in such a way that the labels $$$a_1, a_2, \dots, a_n$$$ form a permutation of $$$1, 2, \dots, n$$$.

You are allowed to modify the labels through the following operation:

1. Choose two distinct integers $$$i$$$ and $$$j$$$ between $$$1$$$ and $$$n$$$.
2. Swap the labels of points $$$i$$$ and $$$j$$$, and finally
3. Draw the segment between points $$$i$$$ and $$$j$$$.

A sequence of operations is valid if after applying all of the operations in the sequence in order, the $$$k$$$-th point ends up having the label $$$k$$$ for all $$$k$$$ between $$$1$$$ and $$$n$$$ inclusive, and the drawn segments don't intersect each other internally. Formally, if two of the segments intersect, then they must do so at a common endpoint of both segments.

In particular, all drawn segments must be distinct.

Find any valid sequence of operations, or say that none exist.

Input format:
The first line contains an integer $$$n$$$ ($$$3 \le n \le 2000$$$)  — the number of points.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$a_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$, $$$1 \le a_i \le n$$$), representing that the $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$ and initially has label $$$a_i$$$.

It is guaranteed that all points are distinct, no three points are collinear, and the labels $$$a_1, a_2, \dots, a_n$$$ form a permutation of $$$1, 2, \dots, n$$$.

Output format:
If it is impossible to perform a valid sequence of operations, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ ($$$0 \le k \le \frac{n(n - 1)}{2}$$$)  — the number of operations to perform, followed by $$$k$$$ lines, each containing two integers $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i\neq j$$$)  — the indices of the points chosen for the operation.

Note that you are not required to minimize or maximize the value of $$$k$$$.

If there are multiple possible answers, you may print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The following animation showcases the first sample test case. The black numbers represent the indices of the points, while the boxed orange numbers represent their labels.

In the second test case, all labels are already in their correct positions, so no operations are necessary.

Example input:
5
-1 -2 2
3 0 5
1 3 4
4 -3 3
5 2 1

Example output:
5
1 2
5 3
4 5
1 5
1 3

Example input:
3
5 4 1
0 0 2
-3 -2 3

Example output:
0

Editorial:
As it turns out, it is always possible to find the required sequence, no matter the position of the points in the plane and the initial permutation.
It turns out that it's pretty hard to analyze even particular positions of the points, and it will be more convenient to start by analyzing particular permutations instead. To this effect, we will begin by doing two things:
1. Ignore every $$$i$$$ such that initially $$$a_i = i$$$. Since we'll prove that the sequence exists for any configuration anyway, they can't ever matter.
2. Draw an arrow from point $$$i$$$ to point $$$a_i$$$ for each $$$i$$$. This divides the points into a bunch of cycles.
Now we can make the following observation:
Observation 1. If we have any cycle, we can get all the balls in that cycle to their correct position by choosing any member $$$i$$$ in the cycle, and repeatedly swap passing between $$$i$$$ and $$$a_i$$$, without generating any intersections.
This allows us to solve the problem for any position of the points as long as the permutation has a single cycle. However, this will generally not be the case. We can hope to deal with this by making a second observation.
Observation 2. If we have any two distinct cycles and any two members $$$u$$$ and $$$v$$$ in those two cycles, then swap passing between $$$u$$$ and $$$v$$$ will merge both cycles.
By combining both observations we can come up with the following general idea to solve any case:
1. First, perform swaps between distinct cycles until all of the cycles merge into a single one.
2. Then, move all the balls to their correct positions as described in the first observation.
Now we just have to figure out how to perform these moves without having intersections between segments. It might be helpful to think about the case when the points are vertices of a convex polygon first since it simplifies the model without sacrificing too much of the geometry. Either way, we will describe only the general case.
Consider any point, which we will use as a "pivot" for the operations at the end. Now, sort all of the other points by the angle of the segment between them and the pivot point. Call the segments that join two consecutive points in the ordering border segments, and the segments between the pivot and the other points central segments. Now we will just merge all the cycles by using border segments and then move all the balls to their intended position by using central segments, this solves the problem.
However, there's one small special case that we might have to deal with depending on how we're thinking about the problem: If the pivot point we chose is on the convex hull of the set of points, then one of the border segments may actually intersect some other segments! Luckily, we can easily prove that this can't happen for more than one of the segments, so our plan still works. There are many different ways to deal with this case. From simplest to most complicated:
• Always choose the bottom-most and left-most point as a pivot. This makes this potentially troublesome segment predictable, and also allows us to slightly simplify the angular sorting code.
• Discard the problematic segment by looking at which pair of consecutive points makes a clockwise turn instead of a counter-clockwise turn.
• Discard the problematic segment by brute-force intersecting each border segment with each central segment. This increases our complexity to $$$\mathcal{O}(n^2)$$$, but this is still fine.
• Intentionally choose a pivot that is not on the convex hull and do something slightly different if the points are the vertices of a convex polygon.
Regardless of how we choose to deal with it, we can now solve the problem with approximately $$$\frac{3}{2}n$$$ operations in the worst case, and a time complexity of either $$$\mathcal{O}(n \log n)$$$ or $$$\mathcal{O}(n^2)$$$ depending on how we implement the solution.