由于涉及到实数，一定，一定不能直接等于，一定，一定加一个误差<0.00001，坑死了……
有两种事物，不难想到用二分图。这里涉及到一个有趣的问题，这个二分图的完美匹配的最小权值和就是答案。为啥呢？因为如果有四个点，a,b,c,d 。Ab和cd交叉，ac和bd不交叉，那么ac和bd的长度和一定小于ab和cd的长度和，可以画一个图很容易就证出来。所以，如果所有的边都不交叉，又因为有解，那么最小的权值和就是解了。附图一枚，自己画的，比较简陋，凑活着看吧……
用KM算法求最佳完美匹配最小权值和，可以直接把所有的权值转成负值，在求最大权值和，但是这种方法我觉得有些不对劲，但是不知道在哪里= =，上网一查，才发现这种方法只能用于x和y数量相同的时候，正统做法应该是用一个很大的数减去每个权值,再求最大权值和。PS：我用的是取反的方法……
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define N 110
struct sss
{
int x,y;
}white[N],black[N];
int n,vx[N],vy[N],fa[N];
double w[N][N],px[N],py[N],str[N];
double dis(int i,int j)
{
return sqrt((double)(black[i].x-white[j].x)*(black[i].x-white[j].x)+(double)(black[i].y-white[j].y)*(black[i].y-white[j].y));
}
int find(int now)
{
int i,j,k;
if (now==)
return ;
vx[now]=;
for (i=;i<=n;i++)
{
if (!vy[i]&&fabs(px[now]+py[i]-w[now][i])<0.00001)
{
vy[i]=;
if (fa[i]==||find(fa[i]))
{
fa[i]=now;
return ;
}
}
else
if (str[i]>px[now]+py[i]-w[now][i])
str[i]=px[now]+py[i]-w[now][i];
}
return ;
}
void KM()
{
int i,j,k,x,y,z;
double na;
memset(fa,,sizeof(fa));
for (i=;i<=n;i++)
{
memset(str,0x7f,sizeof(str));
while ()
{
memset(vx,,sizeof(vx));
memset(vy,,sizeof(vy));
if (find(i))
break;
na=0x7f;
for (j=;j<=n;j++)
if (!vy[j]&&na>str[j])
na=str[j];
for (j=;j<=n;j++)
{
if (vx[j])
px[j]-=na;
if (vy[j])
py[j]+=na;
else
str[j]-=na;
}
}
}
}
int main()
{
int i,j,k,x,y,z;
z=;
while(scanf("%d",&n)!=EOF)
{
if (z)
printf("\n");
else
z=;
for (i=;i<=n;i++)
px[i]=-;
memset(py,,sizeof(py));
for (i=;i<=n;i++)
scanf("%d%d",&white[i].x,&white[i].y);
for (i=;i<=n;i++)
scanf("%d%d",&black[i].x,&black[i].y);
for (i=;i<=n;i++)
for (j=;j<=n;j++)
{
w[i][j]=-dis(i,j);
if (px[i]<w[i][j])
px[i]=w[i][j];
}
KM();
for (i=;i<=n;i++)
printf("%d\n",fa[i]);
}
}