一個非常樸素的 $\mathcal O(n^3)$ 的做法是：隨便連，然後如果有兩個線段相交就交換端點。我們注意到這種交換是朝著某種合法局面單向變化的（不會陷入循環），所以題目條件下必然有解，而且不斷 Check 就可以了。

但是這個太慢了，不過既然都有解，我們就可以考慮分治：找到一條直線切割局面，使得兩邊紅藍點數量相同，然後可以分治下去。

其實這裡已經搞出 $\mathcal O(n \log n)$ 做法了，因為存在高級算法可以求這個線，但是這個太複雜了。

我們考慮只枚舉和坐標軸平行的直線，如果存在就分治。

不存在的話，@Diaosi 老師已經根據零點存在性定理給出了證明，這個時候凸包不可能是一個顏色，所以我們求出凸包匹配一下凸包上的點就可以繼續縮小問題了。

於是我們得到了一個很簡單的 $\mathcal O(n^2)$ 的做法。

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
struct Pt{int x,y,c,i;}A[N];
int n,m,Ans[N],P[N];
inline int Cal(Pt o,Pt A,Pt B){return (A.x-o.x)*(B.y-o.y)-(A.y-o.y)*(B.x-o.x);}
void Work(int L,int R)
{
	if(R<=L)return;
	for(int i=L,t=0;i<=R;i++)
	{
		t+=A[i].c;
		if(t==0&&i!=R)return Work(L,i),Work(i+1,R);
	}
	if(R-L==1)
	{
		if(A[L].c==1)Ans[A[L].i]=A[R].i;
		else Ans[A[R].i]=A[L].i;
		return;
	}
	m=0;
	for(int i=L;i<=R;i++)
	{
		while(m>1&&Cal(A[P[m-2]],A[P[m-1]],A[i])<=0)m--;
		P[m++]=i;
	}
	int T=m;
	for(int i=R-1;i>=L;i--)
	{
		while(m>T&&Cal(A[P[m-2]],A[P[m-1]],A[i])<=0)m--;
		P[m++]=i;
	}
	m--;
	int U=-1,V=-1;
	for(int i=0;i<m;i++)
	{
		int u=P[i],v=P[(i+1)%m];
		if(A[u].c!=A[v].c)
		{
			U=u,V=v;
			break;
		}
	}
	if(A[U].c==-1)swap(U,V);
	Ans[A[U].i]=A[V].i;
	if(U<V)swap(U,V);
	for(int i=U;i<=R;i++)A[i]=A[i+1];
	for(int i=V;i<=R;i++)A[i]=A[i+1];
	Work(L,R-2);
}
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)
	{
		cin>>A[i].x>>A[i].y;
		A[i].c=(i<=n)?1:(-1),A[i].i=i;
	}
	sort(A+1,A+2*n+1,[](Pt A,Pt B){
		if(A.x!=B.x)return A.x<B.x;
		return A.y<B.y;
	});
	Work(1,2*n);
	for(int i=1;i<=n;i++)cout<<Ans[i]-n<<endl;
}