KUPC2012 G : 村

問題概要

N(<2*10^5)個の点がある。このとき、dist(i,j)3*Rが成り立っている。dist(i,j)

解法

異なる連結成分の点は距離が離れているので、ランダムに回転してx座標でソートした後適当に近いところだけを調べていけばよい。
R置きのグリッドを引いて最も近くにある格子点を考えるのが綺麗な解法。

acceptされたコード

int solve2() {
	int origN = N;
	uf.init(N);

	for (int _ = 0; _ < 60; ++_) {
		real theta = rnd.uniform(0, 2*PI);
		for (int i = 0; i < N; ++i) {
			ps[i] = rot(ps[i], theta);
		}
		sort(ps, ps + N);
		for (int i = 0; i < N; ++i) {
			for (int j = 1; j < 10 && i + j < N; ++j) {
				if (ps[i].x + R*1.1 < ps[i+j].y) {
					break;
				}
				if (get_dist(ps[i], ps[i+j]) < 2*R) {
					uf.merge(ps[i].id, ps[i+j].id);
				}
			}
		}

		int M = 0;
		for (int i = 0; i < N; ++i) {
			if (uf.getRoot(ps[i].id) != ps[i].id) {
				continue;
			}
			if ( (i == 0 || ps[i-1].x + R*1.1 < ps[i].x) && (i == N -1 || ps[i].x + R*1.1 < ps[i+1].x)) {
				continue;
			}
			ts[M++] = ps[i];
		}
		for (int i = 0; i < M; ++i) {
			ps[i] = ts[i];
		}
		N = M;
	}

	int ans = 0;
	for (int i = 0; i < origN; ++i) {
		if (uf.getRoot(i) == i) {
			++ans;
		}
	}
	return ans;
}

int main() {
	init();
	printf("%d\n", solve2());

	return 0;
}