D - Swap Pass
先将所有\(a_i==i\)的点都直接去掉
考虑将\(i\)向\(a_i\)连边，那么就会形成一个个的环
考虑只有一个环的情况，那么我们任意固定一个点\(x\)，一直交换\(a_x\)与\(a_{a_x}\)直到\(a_x==x\)，因为所有所有边都交于一点，所以这肯定是合法的
但更普遍的情况是不止有一个环，那么我们考虑交换两个环之间的某两个点的\(a\)，那么这样就可以将两个环合成一个大环，然后继续我们刚才的操作即可
但是有可能环与环之间的边与大环里连的边相交了，考虑如何解决
我们选择最左边的最下的点作为极点\(O\)，然后将其余点根据极角排序
我们用相邻点连边来解决环与环之间的交换，这个可以用并查集维护
然后从极点进行大环的连边，这样显然不存在相交的边
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N=2e3+5;
struct node{
int x,y,a,id;
double angle;
bool operator < (const node &other) const{
return angle<other.angle;
}
}cn[N];
int n,tot,fa[N],to[N];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
fa[x]=y;
}
vector<pii> op;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
++tot,scanf("%d%d%d",&cn[tot].x,&cn[tot].y,&cn[tot].a),cn[tot].id=i;
if(cn[tot].a==i) --tot;
fa[i]=i;
}
if(tot==0) return puts("0"),0;
n=tot;
int st=1;
for(int i=2;i<=n;++i) if(cn[i].x<cn[st].x||(cn[i].x==cn[st].x&&cn[i].y<cn[st].y)) st=i;
swap(cn[1],cn[st]);
for(int i=2;i<=n;++i) cn[i].angle=atan2(cn[i].x-cn[1].x,cn[i].y-cn[1].y);
sort(cn+2,cn+n+1);
for(int i=1;i<=n;++i) merge(cn[i].id,cn[i].a);
for(int i=2;i<n;++i){
int a=find(cn[i].id),b=find(cn[i+1].id);
if(a!=b) merge(a,b),swap(cn[i].a,cn[i+1].a),op.pb({cn[i].id,cn[i+1].id});
to[cn[i].id]=i;
}
to[cn[1].id]=1,to[cn[n].id]=n;
while(cn[1].a!=cn[1].id){
int t=to[cn[1].a];
swap(cn[1].a,cn[t].a),op.pb({cn[1].id,cn[t].id});
}
printf("%d\n",op.size());
for(auto [x,y]:op) printf("%d %d\n",x,y);
return 0;
}