[ZJ][KD Tree] b256. E. 大風吹＠Morris' Blog｜PChome Online 個人新聞台

2014-04-09 12:47:05| 人氣4,591| 回應0 | 上一篇 | 下一篇

[ZJ][KD Tree] b256. E. 大風吹

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

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個人最近椅子的編號，如果一樣近，輸出編號最小的那一個。

範例輸入：

範例輸出：

提示：

出處：

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;
}

我要檢舉

#b256#E #大風吹#最鄰近點對#KD Tree

台長： Morris

您可能對以下文章有興趣

[ZJ] a473. 外援計畫

d807. 方方

[ZJ][BIT+DP] a596. 祖靈要段考了!!!!!!!!

[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢

人氣(4,591) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: ZeroJudge |
此分類上一篇:[ZJ][中線定理] d408. 我要最小值 (Part 2)

回應(0)