2012-12-31 11:51:37Morris
[ITSA桂冠][方格法] a573. ITSA2012 桂冠 元件計算
內容 ：
| 元件計算 |
Background
由於在賽後無法得到題目描述與測資，小光盡可能地將原本題目描述清楚。
The Problem
在平面上給定 N 個相同半徑 R 的圓，如果兩個圓有相交，則它們屬於同一個元件(component)，而詢問有多少個不同的 component。
如圖所示 7 個圓，3 個 component。
輸入說明 ：
測資第一行有一個整數 t，代表接下來有 t 組測試資料。
每組第一行有兩個正整數 N R，分別代表 N 個圓、半徑 R。
接下來有 N 行圓心座標 x, y。
數據範圍 N, x, y <= 60000，R <= 300
測試資料中，圓不會太密集。
輸出說明 ：
對於每組測試資料輸出一行 component 個數。
範例輸入 ：
23 1000 0100 01000 10006 3000 00 600600 0600 60010000 00 10000
範例輸出 ：
23
提示 ：
出處 ：
#include <stdio.h>
#include <vector>
#include <queue>
#define SIZE 601
#define maxx 60000
using namespace std;
struct ND {
int x, y, com;
ND(int a, int b, int c):
x(a), y(b), com(c) {}
};
vector<ND> g[maxx/SIZE+1][maxx/SIZE+1];
int main() {
int t, n, r, 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};
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &r);
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, 0));
}
int res = 0;
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++) {
if(it->com == 0) {
res++;
it->com = res;
queue<ND> Q;
ND tn(0,0,0);
Q.push(*it);
while(!Q.empty()) {
tn = Q.front(), Q.pop();
x = tn.x/SIZE, y = tn.y/SIZE;
for(k = 0; k < 9; k++) {
tx = x+dirx[k], ty = y+diry[k];
if(tx < 0 || ty < 0 || tx > gsize || ty > gsize)
continue;
for(vector<ND>::iterator jt = g[tx][ty].begin();
jt != g[tx][ty].end(); jt++) {
if(jt->com == 0 && (jt->x-tn.x)*(jt->x-tn.x)+(jt->y-tn.y)*(jt->y-tn.y) <= 4*r*r) {
jt->com = res;
Q.push(ND(jt->x, jt->y, res));
}
}
}
}
}
}
}
}
printf("%d\n", res);
}
return 0;
}
/*
2
3 100
0 0
100 0
1000 1000
6 300
0 0
0 600
600 0
600 600
10000 0
0 10000
*/