Codeforces #715 Div1 : D. Swap Pass

なるほど。
https://codeforces.com/contest/1508/problem/D

問題

2次元座標中にN個の点があり、v番の点にはそれぞれ1～NのラベルA[v]が1個ずつある。
これらの点に対し、以下の手順を繰り返し、i番目の点にi番のラベルが来るようにせよ。
なお、3点以上が一直線上に並ぶことはない。

• 2つの点を指定し、ラベルをswapする。その際、2点の間に線分を引く。
• 線分同士が点以外の位置で交差してはならない。

解法

頂点番号iと頂点番号A[i]の間に辺を張ったグラフを考える。
各連結成分内においては、1個固定の点を作り、その点と他の点とのラベルswapを繰り返すことで頂点番号とラベル番号を一致できる。
また、この時明らかに線分同士は交差しない。

連結成分が複数ある場合、2つの連結成分のうち2頂点間のswapを1回行うと、2つの連結成分を連結できる。
そこで、以下のようにする。

• それぞれ連結成分を求める。
• 1つ中心となる連結成分を定め、かつその中で固定の点を定める。
• 中心以外の連結成分について、中心となる連結成分とswapして連結成分を連結していく。その際、他の点と固定点の間を横切らないようにする。
• 1つの連結成分になった後は、最初に書いた通りの手順で条件を満たせる。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<3030> uf;

int N;
ll X[2020],Y[2020],A[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int cand=-1;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>A[i];
		A[i]--;
		uf(i,A[i]);
		if(i!=A[i]) cand=i;
	}
	
	if(cand==-1) return _P("0\n");
	
	vector<pair<double,int>> V;
	FOR(i,N) if(i!=cand && i!=A[i]) {
		double d=atan2(Y[i]-Y[cand],X[i]-X[cand]);
		V.push_back({d,i});
	}
	sort(ALL(V));
	if(V.empty()) {
		cout<<0<<endl;
		return;
	}
	double pi=4*atan(1);
	V.push_back({V[0].first+2*pi,V[0].second});
	vector<pair<int,int>> R;
	
	FOR(i,V.size()-1) {
		if(V[i+1].first-V[i].first>=pi) continue;
		if(uf[V[i].second]!=uf[V[i+1].second]) {
			R.push_back({V[i].second,V[i+1].second});
			uf(V[i].second,V[i+1].second);
			swap(A[V[i].second],A[V[i+1].second]);
		}
	}
	
	while(A[cand]!=cand) {
		x=A[cand];
		R.push_back({cand,x});
		swap(A[cand],A[x]);
	}
	
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<(r.first+1)<<" "<<(r.second+1)<<endl;
	
}

まとめ

こういう幾何は割と好きかもな。