2014-04-09 12:47:05Morris
[ZJ][KD Tree] b256. E. 大風吹
內容 ：
A
跟他的朋友們很喜歡玩團康遊戲，今天他們玩的遊戲是大風吹。規則是這樣的，假設有N個人編號從1到N，一開始每個人會坐在一張編號與自己相同的椅子上，椅
子的位置在座標 ( xi , yi
)，當遊戲開始時你必須離開你的椅子，找到另一把與自己編號不同的椅子坐下，沒找到的人就算輸了。因為A的朋友都是小孩子思想很單純，所以每一次玩的時
候，一定會去搶離自己最近的椅子。所以A想知道離每一個人最近的椅子分別是哪一些，這樣他就可以不費力氣地贏得遊戲。
輸入說明 ：
第
一行有一個整數代表總共有幾筆測試資料。 每一筆測試資料的第1行有一個整數N代表總共有幾個人。
第2行到第N+1行每一行有2個整數x,y，代表每張椅子的座標。 0 < N < 50000, 0 <= x, y <
1000000 每組測試資料之間會有一個空白行。
輸出說明 ：
對每一筆測試資料輸出N行，第i行輸出一個整數代表離第i個人最近椅子的編號，如果一樣近，輸出編號最小的那一個。
範例輸入 ：
2 3 0 0 1 1 2 2 3 0 0 2 2 3 3
範例輸出 ：
2 1 2 2 3 2
提示 ：
出處 ：
2009 NPSC 高中組決賽
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
.
.
.
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
...
搜尋最鄰近的 M 對時，努力地估價吧！
由於每次劃分的維度不同，要保留前幾次在某維度的估價情況。
/**********************************************************************************/
/* Problem: b256 "E. 大風吹" from 2009 NPSC 高中組決賽 */
/* Language: CPP (2999 Bytes) */
/* Result: AC(4.4s, 1.8MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-09 12:43:25 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node {
Node *l, *r;
int idx;
};
Node buf[50005];
int bufsize;
int pt[50005][5];
int L[5];
int N, K, M;
int A[50005];
int sortIdx;
bool cmp(int a, int b) {
return pt[a][sortIdx] < pt[b][sortIdx];
}
Node* kdTreebuild(int k, int l, int r) {
if(l > r)
return NULL;
sortIdx = k;
sort(A+l, A+r+1, cmp);
int m = (l + r)/2;
Node *ret = &buf[bufsize++];
ret->idx = A[m]; // point index
if(l != r) {
ret->l = kdTreebuild((k+1)%K, l, m-1);
ret->r = kdTreebuild((k+1)%K, m+1, r);
} else {
ret->l = ret->r = NULL;
}
return ret;
}
int max_dist = 0x3f3f3f3f, banIdx;
int dist(int idx) {
if(banIdx == idx)
return 0x3f3f3f3f;
int ret = 0;
for(int i = 0; i < K; i++)
ret += (pt[idx][i] - L[i]) * (pt[idx][i] - L[i]);
return ret;
}
int h_function(int h[]) {
int ret = 0;
for(int i = 0; i < K; i++)
ret += h[i];
return ret;
}
struct pQcmp {
bool operator() (int a, int b) {
int d1 = dist(a);
int d2 = dist(b);
if(d1 != d2)
return d1 < d2;
return a < b;
}
};
priority_queue<int, vector<int>, pQcmp> pQ;
void DC(Node *nd, int k, int h[]) {
if(nd == NULL || h_function(h) >= max_dist)
return;
int d = dist(nd->idx);
if(d < max_dist) {
pQ.push(nd->idx);
if(pQ.size() == M+1) {
max_dist = dist(pQ.top());
pQ.pop();
}
}
int hk = h[k];
if(L[k] < pt[nd->idx][k]) {
if(nd->l != NULL)
DC(nd->l, (k+1)%K, h);
if(nd->r != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->r, (k+1)%K, h);
h[k] = hk;
}
} else {
if(nd->l != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->l, (k+1)%K, h);
h[k] = hk;
}
if(nd->r != NULL)
DC(nd->r, (k+1)%K, h);
}
}
int main() {
K = 2;
scanf("%*d");
while(scanf("%d", &N) == 1) {
int i, j, k;
for(i = 0; i < N; i++) {
for(j = 0; j < K; j++)
scanf("%d", &pt[i][j]);
A[i] = i;
}
bufsize = 0;
Node *root = kdTreebuild(0, 0, N-1);
int cutCond[50005];
for(i = 0; i < N; i++)
cutCond[i] = 0x3f3f3f3f;
for(i = 0; i < N; i++) {
M = 1;
max_dist = 0x3f3f3f3f;
banIdx = i;
for(j = 0; j < K; j++)
L[j] = pt[i][j];
int h[5] = {};
DC(root, 0, h);
int best = pQ.top();
pQ.pop();
cutCond[best] = min(cutCond[best], max_dist + 1);
printf("%d\n", best + 1);
}
}
return 0;
}
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
.
.
.
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
...
搜尋最鄰近的 M 對時，努力地估價吧！
由於每次劃分的維度不同，要保留前幾次在某維度的估價情況。
/**********************************************************************************/
/* Problem: b256 "E. 大風吹" from 2009 NPSC 高中組決賽 */
/* Language: CPP (2999 Bytes) */
/* Result: AC(4.4s, 1.8MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2014-04-09 12:43:25 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node {
Node *l, *r;
int idx;
};
Node buf[50005];
int bufsize;
int pt[50005][5];
int L[5];
int N, K, M;
int A[50005];
int sortIdx;
bool cmp(int a, int b) {
return pt[a][sortIdx] < pt[b][sortIdx];
}
Node* kdTreebuild(int k, int l, int r) {
if(l > r)
return NULL;
sortIdx = k;
sort(A+l, A+r+1, cmp);
int m = (l + r)/2;
Node *ret = &buf[bufsize++];
ret->idx = A[m]; // point index
if(l != r) {
ret->l = kdTreebuild((k+1)%K, l, m-1);
ret->r = kdTreebuild((k+1)%K, m+1, r);
} else {
ret->l = ret->r = NULL;
}
return ret;
}
int max_dist = 0x3f3f3f3f, banIdx;
int dist(int idx) {
if(banIdx == idx)
return 0x3f3f3f3f;
int ret = 0;
for(int i = 0; i < K; i++)
ret += (pt[idx][i] - L[i]) * (pt[idx][i] - L[i]);
return ret;
}
int h_function(int h[]) {
int ret = 0;
for(int i = 0; i < K; i++)
ret += h[i];
return ret;
}
struct pQcmp {
bool operator() (int a, int b) {
int d1 = dist(a);
int d2 = dist(b);
if(d1 != d2)
return d1 < d2;
return a < b;
}
};
priority_queue<int, vector<int>, pQcmp> pQ;
void DC(Node *nd, int k, int h[]) {
if(nd == NULL || h_function(h) >= max_dist)
return;
int d = dist(nd->idx);
if(d < max_dist) {
pQ.push(nd->idx);
if(pQ.size() == M+1) {
max_dist = dist(pQ.top());
pQ.pop();
}
}
int hk = h[k];
if(L[k] < pt[nd->idx][k]) {
if(nd->l != NULL)
DC(nd->l, (k+1)%K, h);
if(nd->r != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->r, (k+1)%K, h);
h[k] = hk;
}
} else {
if(nd->l != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->l, (k+1)%K, h);
h[k] = hk;
}
if(nd->r != NULL)
DC(nd->r, (k+1)%K, h);
}
}
int main() {
K = 2;
scanf("%*d");
while(scanf("%d", &N) == 1) {
int i, j, k;
for(i = 0; i < N; i++) {
for(j = 0; j < K; j++)
scanf("%d", &pt[i][j]);
A[i] = i;
}
bufsize = 0;
Node *root = kdTreebuild(0, 0, N-1);
int cutCond[50005];
for(i = 0; i < N; i++)
cutCond[i] = 0x3f3f3f3f;
for(i = 0; i < N; i++) {
M = 1;
max_dist = 0x3f3f3f3f;
banIdx = i;
for(j = 0; j < K; j++)
L[j] = pt[i][j];
int h[5] = {};
DC(root, 0, h);
int best = pQ.top();
pQ.pop();
cutCond[best] = min(cutCond[best], max_dist + 1);
printf("%d\n", best + 1);
}
}
return 0;
}