AOJ 2412 - Village

問題文 : 村

解法 :
Rによってブロック分けをする.
近傍の8ブロックを1つのグループとみなして, このグループの数を幅優先探索で求める.
setを使っているので, O(NlogN)時間で探索を終えることが出来る.

コード :

#include <cstdio>
#include <cmath>
#include <set>

using namespace std;

int main()
{
	int N;
	double R;
	int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
	int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
	
	scanf("%d %lf", &N, &R);
	
	set<pair<int, int> > g;
	
	for (int i = 0; i < N; i++){
		double x, y;
		scanf("%lf %lf", &x, &y);
		int nx = (int)floor(x / R), ny = (int)floor(y / R);
		g.insert(make_pair(nx, ny));
	}
	
	int ans = 0;
	
	set<pair<int, int> >::iterator it = g.begin();
	
	for(;it != g.end(); it++){
		ans++;
		int sx = it->first, sy = it->second;
		for (int i = 0; i < 8; i++){
			int tx = sx + dx[i], ty = sy + dy[i];
			if (g.find(make_pair(tx, ty)) != g.end()){
				g.erase(make_pair(tx, ty));
			}
		}
	}
	
	printf("%d\n", ans);
	
	return (0);
}