KUPC2012 G : 村
問題概要
N(<2*10^5)個の点がある。このとき、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; }