[NPSC][方格法] b256. E. 大風吹＠Morris' Blog

2012-12-30 08:28:22| 人氣956| 回應0 | 上一篇 | 下一篇

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

範例輸入： help

範例輸出：

提示：

出處：

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
*/

我要檢舉

#b256#E. 大風吹#方格法

台長： Morris

您可能對以下文章有興趣

[ZJ] a361. A. 賓果遊戲

[ZJ][翻轉處理] a315. D 滿州國皇帝之璽

b046. E. 智慧型單字查詢

b094. H. 數字拼盤 (IDA* 版本)

人氣(956) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[ZJ][KM算法] d210. 老問題
此分類上一篇:[ZJ][DLX][最少重覆覆蓋] b199. D. 郵輪

回應(0)