AtCoder ABC #373 : G - No Cross Matching

これ想定解かな…。
https://atcoder.jp/contests/abc373/tasks/abc373_g

問題

2次元座標上で2N個の点の位置が与えられる。
一直線上に3点以上が並ぶことがない。
前半N個と後半N個の点をペアにして線分を引くとき、線分同士が交差しないようにできるか。
できるなら組み合わせの一例を示せ。

解法

適当にペアにした後、交差を見つけたらペア相手をswapする、を繰り返すと良い。
swapすると線分の長さの総和が短くなるので、無限ループすることはない。

int N;
int A[603],B[603];
int R[303];

int cross(int a,int b,int c,int d) {
	ll XX[3],YY[3];
	XX[0]=A[b]-A[a]; YY[0]=B[b]-B[a];
	XX[1]=A[c]-A[a]; YY[1]=B[c]-B[a];
	XX[2]=A[d]-A[a]; YY[2]=B[d]-B[a];
	ll c1=XX[0]*YY[1]-XX[1]*YY[0];
	ll c2=XX[0]*YY[2]-XX[2]*YY[0];
	if(c1>0&&c2>0||c1<0&&c2<0) return 0;
	XX[0]=A[d]-A[c]; YY[0]=B[d]-B[c];
	XX[1]=A[a]-A[c]; YY[1]=B[a]-B[c];
	XX[2]=A[b]-A[c]; YY[2]=B[b]-B[c];
	c1=XX[0]*YY[1]-XX[1]*YY[0];
	c2=XX[0]*YY[2]-XX[2]*YY[0];
	if(c1>0&&c2>0||c1<0&&c2<0) return 0;
	return 1;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>A[i]>>B[i];
	FOR(i,N) cin>>A[N+i]>>B[N+i];
	FOR(i,N) R[i]=N+i;
	sort(V,V+N,cmp);
	int up=1;
	while(up) {
		up=0;
		FOR(i,N) FOR(j,i) if(cross(i,R[i],j,R[j])) swap(R[i],R[j]), up=1;
	}
	FOR(i,N) FOR(j,i) assert(cross(i,R[i],j,R[j])==0);
	FOR(i,N) cout<<R[i]+1-N<<" ";
	cout<<endl;
}

まとめ

凸包とか使うかな…と思ったけど、使わずに済んでしまった。