1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 110 12 #define LL long long 13 #define INF 9999999999.0 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     int x,y; 20     //point(int x=0,int y=0):x(x),y(y){} 21 }p[N<<1]; 22 double dis(point a,point b) 23 { 24     return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y)); 25 } 26 double dcmp(double x) 27 { 28     if(fabs(x)<eps) return 0; 29     return x<0?-1:1; 30 } 31 double w[N][N]; 32 int n,link[N],x[N],y[N]; 33 double lx[N],ly[N],slack[N],d; 34 bool match(int u) 35 { 36     x[u] = 1; 37     for(int i = 1; i <= n ; i++) 38     { 39         if(y[i]) continue; 40         double o = lx[u]+ly[i]-w[u][i]; 41         if(dcmp(o)==0) 42         { 43             y[i] = 1; 44             if(!link[i]||match(link[i])) 45             { 46                 link[i] = u; 47                 return true; 48             } 49         } 50         else if(slack[i]>o) slack[i] = o; 51     } 52     return false; 53 } 54 void km() 55 { 56     int i,j; 57     for(i = 1 ;i <= n ;i++) 58     lx[i] = -INF; 59     memset(ly,0,sizeof(ly)); 60     memset(link,0,sizeof(link)); 61     for(i = 1; i <= n ;i++) 62         for(j = 1; j <= n ;j++) 63         lx[i] = max(lx[i],w[i][j]); 64     for(i = 1; i <= n ;i++) 65     { 66         for(j = 1; j <= n;j++) 67         slack[j] = INF; 68         for(;;) 69         { 70              d = INF; 71             memset(x,0,sizeof(x)); 72             memset(y,0,sizeof(y)); 73             if(match(i)) break; 74             for(j =1 ; j <= n ;j++) 75             if(!y[j]&&d>slack[j]) d =min(d,slack[j]); 76             for(j =1 ;j <= n ;j++) if(x[j]){lx[j]-=d;} 77             for(j =1 ;j <= n ;j++) if(y[j]){ly[j]+=d;} 78            // else slack[j]-=d; 79             //cout<<","; 80         } 81     } 82 } 83  84 int main() 85 { 86     int i,j; 87     while(scanf("%d",&n)!=EOF) 88     { 89         //init(); 90         for(i = 1; i <=n+n; i++) 91         scanf("%d%d",&p[i].x,&p[i].y); 92         for(i  =1; i <= n ;i++) 93             for(j = 1; j <= n ; j++) 94             { 95                 w[i][j] = -dis(p[i+n],p[j]); 96             } 97         km(); 98         for(i = 1; i <= n ;i++) 99         printf("%d\n",link[i]);100     }101     return 0;102 }