Codeforces1508D - Swap Pass

Posted on Edited on In

Codeforces1508D - Swap Pass

题目大意：

给定 \(n\) 个不共线的点 \(p_i\) ，和一个排列 \(a_i\)

每次交换 \(a_i,a_j\) 的同时，在 \(p_i,p_j\) 之间连一条线段

求一个方案使得最后 \(a_i=i\) ，且连的线之间不交叉

\[ \ \]

问题解决分为两步：

1.环的交换

对于 \(a_i\) 的处理，显然可以将所有点分为若干由 \((i,a_i)\) 边构成的环

每个环上可以随意选择一个点作为初始，设其为 \(o\)

每次交换 \(o,a_o\) 上的数，这样的过程就变成了 \(a_o\) 在环上走一圈

最后连出的边就是 \(o\) 向环上每一个点连接的一圈 "射线"

2.环的合并

考虑Simple的情况，交换两个环上的某一对元素可以将两个环合并在一起

我们希望通过在最终的射线里找"缝隙"连线来合并所有的环

取某一个非孤立的点为原点 \(o\) ，考虑先将所有点放到同一个环里

具体的，将所有的点按原点极角排序，除了最多一个跨过 \(>\pi\) 的位置不能连

剩下的点总可以和极角相邻的点交换，所连的线总在最终射线之间构成三角形

通过若干这样的交换就可以合并到一起

最后再对于钦定的原点进行一次环交换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10;

int n,m,O;
int A[N],I[N];
struct Node{
	int x,y;
	Node(){}
	Node(int x,int y):x(x),y(y){}
	Node operator + (const Node _) const { return Node(x+_.x,y+_.y); }
	Node operator - (const Node _) const { return Node(x-_.x,y-_.y); }
	ll operator * (const Node _) const { return 1ll*x*_.x+1ll*y*_.y; }
	db angle() const { return atan2(y,x); }
} P[N];

int C,X[N],Y[N],F[N];
void Swap(int x,int y){ swap(A[x],A[y]),X[++C]=x,Y[C]=y; }
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
void Union(int x,int y){ F[Find(y)]=Find(x); }

int main(){
	n=rd();
	rep(i,1,n) P[i].x=rd(),P[i].y=rd(),A[i]=rd();
	rep(i,1,n) if(A[i]!=i) O=i;
	if(!O) return puts("0"),0;
	rep(i,1,n) if(i!=O) P[i]=P[i]-P[O],I[++m]=i;
	rep(i,1,n) F[i]=i;
	rep(i,1,n) if(F[i]==i) for(int j=A[i];j!=i;j=A[j]) Union(i,j);
	sort(I+1,I+m+1,[&](int x,int y){ return P[x].angle()<P[y].angle(); });
	rep(i,1,m) if(P[I[i]]*P[I[i%m+1]]>=0 && Find(I[i])!=Find(I[i%m+1])) Union(I[i],I[i%m+1]),Swap(I[i],I[i%m+1]);
	while(A[O]!=O) Swap(A[O],O);
	printf("%d\n",C);
	rep(i,1,C) printf("%d %d\n",X[i],Y[i]);
}