先忽略掉所有 \(a_i = i\) 的点。
考虑我们钦定一个点 \(s\)，每次与 \(a_s\) 换直到 \(a_s = s\) 为止。不难发现这样相当于在置换环上删掉 \(a_s\) 这个点。这样可以解决 \(s\) 所在的环。
问题是可能会形成很多个环。
我们把其他点按照 \(s\) 极角排序，注意此处 \(s\) 应选取横坐标最小的点，作用是保证不存在两点夹角 \(> \pi\)。排序后如果相邻的点不在同一个连通块就交换它们。容易发现对于不在同一个置换环上的两个点，交换它们的 \(a_i\) 相当于合并这两个环。
交换完一遍后容易发现只存在一个大的置换环。然后我们就做一遍开头所述算法即可。
使用并查集维护连通性即可。
code
// Problem: D. Swap Pass
// Contest: Codeforces - Codeforces Round 715 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1508/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 2020;
ll n, fa[maxn], d[maxn];
struct node {
ll x, y, id;
db ang;
} a[maxn], b[maxn], c[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
}
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", &c[i].x, &c[i].y, &d[i]);
c[i].id = i;
fa[i] = i;
}
for (int i = 1; i <= n; ++i) {
merge(i, d[i]);
}
int tot = 0;
for (int i = 1; i <= n; ++i) {
if (d[i] != i) {
b[++tot] = c[i];
}
}
if (!tot) {
puts("0");
return;
}
int p = 1;
for (int i = 2; i <= tot; ++i) {
if (b[i].x < b[p].x || (b[i].x == b[p].x && b[i].y < b[p].y)) {
p = i;
}
}
int tt = 0;
for (int i = p; i <= tot; ++i) {
a[++tt] = b[i];
}
for (int i = 1; i < p; ++i) {
a[++tt] = b[i];
}
for (int i = 2; i <= tot; ++i) {
a[i].ang = atan2(a[i].y - a[1].y, a[i].x - a[1].x);
}
sort(a + 2, a + tot + 1, [&](node a, node b) {
return a.ang < b.ang;
});
vector<pii> ans;
for (int i = 2; i < tot; ++i) {
if (find(a[i].id) != find(a[i + 1].id)) {
ans.pb(a[i].id, a[i + 1].id);
swap(d[a[i].id], d[a[i + 1].id]);
merge(a[i].id, a[i + 1].id);
}
}
while (d[a[1].id] != a[1].id) {
ans.pb(a[1].id, d[a[1].id]);
swap(d[a[1].id], d[d[a[1].id]]);
}
printf("%d\n", (int)ans.size());
for (pii p : ans) {
printf("%d %d\n", p.fst, p.scd);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}