解題區/出題解題

[ACM 題目] 最近餐館

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

每到吃飼料時間，某 M 正思考要去哪裡解決，雖然有很多很多地方可以去吃，由於某 M 對於美食沒有特別需求，所以只會到最近的幾個地點即可，然後再以循環輪食的方式日復一日。

某 M 現在的位置與每個餐館的位置都用一個笛卡爾坐標系中的點表示，每個點與每個點的距離為歐幾里得距離。

x = (x1,…,xn) 和 y = (y1,…,yn) 之間的距離為

test

現給出在 K 維空間中某 M 所處的位置座標，以及 N 個餐館位置，請觀察某 M 會到哪裡吃飼料。.

Input

輸入有多組測資，

每一組第一行會有兩個整數 N, K，

接下來會有 N 行，每行包含 K 個整數，表示第 i 個餐館座標。

接下來一行，包含一個整數 Q，表示某 M 的可能座標 。

接下來會有 Q 行，每一組詢問會有兩行，第一行會有 K 個整數，表示某 M 所在的座標，第二行會有一個整數 P。

(N < 8192, K < 6, Q < 10,000, P < 11, 座標值 0 < x, y < 10,000)

Output

對於每一組詢問，輸出一行 Case #:，第一個整數為 P，接下來 P 個整數按照距離由小到大輸出餐館編號，如果相同則輸出編號小的。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

Sample Output

1
2
3
Case 1: 1 1
Case 2: 2 2 3
Case 3: 1 2

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8192
#define MAXD 8
#define INF 0x3f3f3f3f
class kdTree {
    public:	
    struct PointD {
        int d[MAXD];
        int label;
    };
    struct Node {
    	Node *lson, *rson;
    	int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
    		return x->d[sortDidx] < y->d[sortDidx];
        }
    };
    struct pQcmp {
        bool operator() (pair<int, int> &a, pair<int, int> &b) const {
        	if (a.first != b.first)	return a.first < b.first;
        	return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<int, int>, vector< pair<int, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K;
    int Q[MAXD], max_dist, qM;
    void prepare(int n) {
        bufsize = 0;
        for (int i = 0; i < n; i++)
        	A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    int dist(int idx) {
        int ret = 0;
        for(int i = 0; i < K; i++)
            ret += (pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    int h_func(int h[]) {
        int ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, int h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        int d = dist(u->label);
        if (d < max_dist) {
            pQ.push(make_pair(d, u->label));
            if (pQ.size() == qM + 1) {
                max_dist = pQ.top().first, pQ.pop();
            }
        }
        int old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
        }
    }
    void query(int p[], int M) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        int h[MAXD] = {};
        findNearest(root, 0, h);
        printf("%d", M);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = ret.size() - 1; i >= 0; i--)
        	printf(" %d", ret[i] + 1);
        puts("");
    }
};	
int kdTree::sortDidx;
kdTree tree;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, q, p[MAXD], x;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
    	tree.K = m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			scanf("%d", &tree.pt[i].d[j]);
    		tree.pt[i].label = i;
    	}
    	tree.prepare(n);
        scanf("%d", &q);
        while (q--) {
        	for (int i = 0; i < m; i++)
        		scanf("%d", &p[i]);
        	scanf("%d", &x);
        	printf("Case %d: ", ++cases);
        	tree.query(p, x);
        }
    }
    return 0;
}
/*
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
*/