2012-12-30 08:28:22Morris

[NPSC][方格法] 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個人最近椅子的編號,如果一樣近,輸出編號最小的那一個。

範例輸入 :help

2
3
0 0
1 1
2 2

3
0 0
2 2
3 3

範例輸出 :

2
1
2
2
3
2

提示 :

出處 :

2009 NPSC 高中組決賽

測資有重覆點,錯得有點莫名奇妙,還以為是我算法錯了,沒想到椅子可以疊在同一個點上。

至於方格法怎麼寫,就是將 [x/SIZE][y/SIZE] 串接這個點,找鄰近點得時候包含自己那格搜整個九宮格,
如果這九宮格裡面還沒有點,則在繼續擴大。

/**********************************************************************************/
/*  Problem: b256 "E. 大風吹" from 2009 NPSC 高中組決賽                   */
/*  Language: CPP (2974 Bytes)                                                    */
/*  Result: AC(980ms, 1.7MB) judge by this@ZeroJudge                              */
/*  Author: morris1028 at 2012-12-30 07:42:33                                     */
/**********************************************************************************/


#include <stdio.h>
#include <vector>
#include <queue>
#define SIZE 500
#define maxx 100000
using namespace std;
struct ND {
    int x, y, idx;
    ND(int a, int b, int c) :
    x(a), y(b), idx(c) {}
};
struct PT {
    int x, y;
    PT(int a, int b) :
    x(a), y(b) {}
};
vector<ND> g[maxx/SIZE+1][maxx/SIZE+1];
int main() {
    int t, n, x, y, tx, ty;
    int i, j, k;
    int gsize = maxx/SIZE;
    int dirx[9] = {0,0,0,1,1,1,-1,-1,-1};
    int diry[9] = {0,1,-1,0,1,-1,0,1,-1};
    int out[50005];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i <= gsize; i++)
            for(j = 0; j <= gsize; j++)
                g[i][j].clear();
        for(i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            g[x/SIZE][y/SIZE].push_back(ND(x, y, i));
        }
        char used[201][201] = {}; // gsize
        for(i = 0; i <= gsize; i++) {
            for(j = 0; j <= gsize; j++) {
                for(vector<ND>::iterator it = g[i][j].begin();
                    it != g[i][j].end(); it++) {
                    //printf("%d %d\n", it->x, it->y);
                    queue<PT> Q, CLR;
                    PT tn(0,0);
                    Q.push(PT(i, j));
                    long long r = 1LL<<60, dist;
                    int label, flag;
                    while(!Q.empty()) {
                        tn = Q.front(), Q.pop();
                        CLR.push(tn);
                        x = tn.x, y = tn.y;
                        flag = 0;
                        for(vector<ND>::iterator jt = g[x][y].begin();
                            jt != g[x][y].end(); jt++) {
                            dist = (it->x-jt->x)*(it->x-jt->x)+(it->y-jt->y)*(it->y-jt->y);
                            if(jt->idx != it->idx && (dist < r || dist == r && jt->idx < label)) {
                                r = dist;
                                label = jt->idx;
                                flag = 1;
                            }
                        }
                        if(flag) {
                            for(k = 0; k < 9; k++) {
                                tx = x+dirx[k], ty = y+diry[k];
                                if(tx < 0 || ty < 0 || tx > gsize || ty > gsize)
                                    continue;
                                if(used[tx][ty])
                                    continue;
                                Q.push(PT(tx, ty));
                            }
                        }
                    }
                    while(!CLR.empty()) {
                        tn = CLR.front(), CLR.pop();
                        used[tn.x][tn.y] = 0;
                    }
                    out[it->idx] = label;
                }
            }
        }
        for(i = 0; i < n; i++)
            printf("%d\n", out[i]+1);
    }
    return 0;
}
/*
2
3
0 0
1 1
2 2
3
0 0
2 2
3 3
*/