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個人最近椅子的編號，如果一樣近，輸出編號最小的那一個。
範例輸入
：
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
*/
測資有重覆點，錯得有點莫名奇妙，還以為是我算法錯了，沒想到椅子可以疊在同一個點上。
至於方格法怎麼寫，就是將 [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
*/