1:最近餐馆

描述

每到饭点，就又到了一日几度的小L纠结去哪吃饭的时候了。因为有太多太多好吃的地方可以去吃，而小L又比较懒不想走太远，所以小L会先找到距离他最近的M家餐馆然后再做筛选。

小L现在所在的位置和每家餐馆的位置用同一笛卡尔坐标系中的点表示，而点与点之间的距离为欧几里得距离，对于点p = (p1, p2,..., pn)和点q = (q1,q2,..., qn)，两者的距离定义如下

现给出在K维空间中小L所处的位置的坐标以及n个餐馆的位置，请帮助小L完成他的需求。

输入

第1行包含两个整数n和K，1≤n≤5000，1≤K≤5。
接下来n行，每行包含K个数，表示每个餐馆的坐标。
接下来1行，包含一个数t，1≤t≤10000，表示小L询问的数目。
每次询问包括两行。第1行包含K个数，表示小L所在的坐标。第2行包含一个数M，1≤M≤10。
所有坐标值不会超过10000。
输入数据包含多组数据，请逐个处理直到文件结束。

输出

对于每一个询问，输出m+1行：
第1行输出：”the closest M points are:”，其中M在输入中给出。
接下来M行输出距离最近的M家餐馆的坐标，按照由近及远的顺序输出。
输出数据保证答案唯一。保证从小L的位置到最近的M+1家餐馆位置各不相同，这说明如下输入数据：
2 2
1 1
3 3
1
2 2
1
不会存在。

样例输入

3 2
1 1
1 3
3 4
2
2 3
2
2 3
1

样例输出

the closest 2 points are:
1 3
3 4
the closest 1 points are:
1 3

2:四分树

描述

一幅如图2(a)所示的二进制图片常常会用一个二进制矩阵来表示。所谓二进制矩阵是指矩阵中的每一个数不是0就是1。图2(b)展示图2(a)用二进制矩阵表示的情况。

图2：(a)二进制图片(b)图片的矩阵表示(c)四分树划分(d)四分树表示

 

为了保存图2(b)这样的矩阵，经常使用四分树来完成。对于一个N * N的矩阵，N <= 512且N = 2^i（i为正整数），如果这个矩阵中的数不全一样，那么我们会把这个矩阵分成4个N/2 * N/2的矩阵，如图2(c)所示。之后，我们再对这4个N/2 * N/2的矩阵划分，同样地，如果里面的数不全一样则划分成N/4 * N/4的矩阵。图2(c)里面右边的两个N/2 * N/2的矩阵就被这样再度划分了。如此可以持续进行划分，直到里面的数全一样。图2(c)展示了完全划分完毕的样子。

我们一般都将二进制图片存成图2(d)这样的四分树的形式，这棵树是通过图2(c)里面的划分得到的。图2(d)里面的每一个结点都代表图2(c)里面的矩阵，而树的根结点代表整个大的矩阵。如果树中一个结点的值为1，则代表这个结点对应的矩阵需要划分成4个小矩阵。否则，这个结点将包含两个数。第一个数为0，表示不用再划分，第二个数为0或者1，表示整个矩阵都是这个值。整棵树可以用它的宽度优先遍历得到的结果来表示，如图2(d)中的树可以表示成(1)(0,0)(1)(0,1)(1)(0,0)(0,1)(1)(0,0)(0,0)(0,0)(0,1)(0,1)(0,0)(0,1)(0,0)(0,1)。删掉括号和逗号，我们可以得到一个更简短的纯二进制编码100101100011000000010100010001来编码这张图片，它的16进制形式为258C0511。

现在请你编写一个程序，求出给定图片的16进制形式的编码。

 

输入

第1行包含一个数k，1 <= k <= 100，表示数据的组数。
对于每一组数据，第1行包含一个数N表示图片的大小为N * N，其中N <= 512且N = 2^i（i为正整数）。
接下来跟着一个N * N的矩阵代表一张二进制图片。每两个0和1之间至少有一个空格。

输出

每张图片通过四分树得到的16进制编码。

样例输入

3
2
0 0
0 0
4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
8
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

样例输出

0
114
258C0511

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[512][512];
int tree[1048576+5];
char code[1048576], *codeptr;
int dfs(int k, int lx, int rx, int ly, int ry) {
    if(lx > rx || ly > ry)    return 0;
    if(lx == rx && ly == ry) {
        tree[k] = g[lx][ly];
        return g[lx][ly];
    }
    int mx = (lx + rx)/2;
    int my = (ly + ry)/2;
    int s = 0;
    s += dfs((k<<2), lx, mx, ly, my);
    s += dfs((k<<2)+1, lx, mx, my+1, ry);
    s += dfs((k<<2)+2, mx+1, rx, ly, my);
    s += dfs((k<<2)+3, mx+1, rx, my+1, ry);
    tree[k] = s;
    return s;
}
void bfs(int k, int lx, int rx, int ly, int ry) {
    queue<int> K, W, H;
    K.push(k), W.push(rx-lx+1), H.push(ry-ly+1);
    int h, w;
    while(!K.empty()) {
        k = K.front(), K.pop();
        w = W.front(), W.pop();
        h = H.front(), H.pop();
        if(tree[k] == w*h || tree[k] == 0) {
            *codeptr++ = '0';
            *codeptr++ = (tree[k] != 0) + '0';
            continue;
        }
        *codeptr++ = '1';
        K.push(k<<2), W.push(w/2), H.push(h/2);
        K.push((k<<2)+1), W.push(w/2), H.push(h/2);
        K.push((k<<2)+2), W.push(w/2), H.push(h/2);
        K.push((k<<2)+3), W.push(w/2), H.push(h/2);
    }
}
int main() {
    int testcase;
    int n;
    int i, j, k;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        int f = dfs(1, 0, n-1, 0, n-1);
        codeptr = code;
        bfs(1, 0, n-1, 0, n-1);
        *codeptr = '\0';
        int len = strlen(code), counter = len%4;
        int output = 0;
        if(counter == 0)    counter = 4;
        //printf("%s\n", code);
        for(i = 0; i < len; i++) {
            output = output<<1 | (code[i]-'0');
            if(--counter == 0) {
                printf("%X", output);
                output = 0;
                counter = 4;
            }
        }
        puts("");
    }
    return 0;
}