http://codeforces.com/problemset/problem/200/A

       好题，虽然我又没独立想出来=。=。。给一个n*m的点矩阵，询问K次，每个输入一个坐标x,y，寻找一个于该坐标曼哈顿距离最小且未被占有的点，并占有它。

      做法是每次询问从x开始往左右暴力枚举横坐标，直到横坐标绝对值差已经大于当前答案。可以保证第i个询问，最多只需要向两边枚举sqrt(i)次。同时可以利用并查集，对于每个横坐标O（1）求出最接近的点。。最后当n比m大很多时候算法会退化，此时可以通过交换横竖坐标来解决。

1 //By Lin 2 #include
      
        3 #include
       
         4 #include
        
          5 #define maxn 2005 6 #define inf  0x7fffffff 7 using namespace std; 8  9 bool    flag = false;10 int        n,m,K;11 int        up[maxn][maxn],down[maxn][maxn];12 int        Find(int p[],int x){13     return p[x] != x?p[x]=Find(p,p[x]):x;14 }15 16 void    check(int x,int y,int i,int &g,int &h ,int &L ){17     if ( i < 1 || i > n ) return;18     int j;19     j = Find(up[i],y);20     if ( j != 0 ) {21         int d = abs(x-i)+abs(y-j);22         if ( d < L || d == L && ( !flag&&(i
         
           m ) {36         swap(n,m); 37         flag = true;38     }39     for (int i = 1; i<=n; i++) 40         for (int j = 0; j<=m+1; j++) up[i][j] = down[i][j] = j; 41     while ( K -- ){42         int x , y; 43         scanf("%d%d", &x, &y );44         if ( flag ) swap(x,y);45         int g = -1 , h = -1 , L = inf; 46         for (int i = 0; i<=L; i++){47             check( x , y , x-i , g , h , L );48             check( x , y , x+i , g , h , L );49         }50         up[g][h] = h-1;51         down[g][h] = h+1;52         if ( flag ) swap(g,h);53         printf("%d %d\n" , g , h );54     }55     return 0;56 }