Atcoder Regular Contest 010 D - 情報伝播

問題

日本語なので本文参照（http://arc010.contest.atcoder.jp/tasks/arc010_4）

座標平面上に味方n人と敵m人がいる。
それぞれの座標が与えられる。

味方は、自分から最も近い敵よりも、厳密に近くにいる味方全員に情報を伝えられる。
味方全員に情報を伝えたいとき、最初に情報を伝えるべき味方の数の最小値はいくつか。

制約条件

n≦4000
m≦100000
座標の絶対値は10^9以下
m＞1000のとき、敵は10^9以下の範囲にランダムに散らばっている

方針

それぞれの味方ごとに、最も近い敵が短い時間で求められれば、
有向グラフを作ることができるので、あとは強連結成分分解して入次数0の頂点を数えればそれが答えになる。

最も近い敵はバケット法で求めた。
敵が一様分布していることが保証されているので、
平面を適当にバケットに区切ってやれば、どのバケットに入る敵の期待値も同じになる。
なので、適当に自分の周囲のバケットだけを見れば、最も近い敵が短い時間でわかる。

ソースコード

int n, m;
int x[5000], y[5000];
int sx[100000], sy[100000];
vector<vi> g;

vi s[30][30];

inline ll dist(ll x, ll y){
	return x * x + y * y;
}

int main(){
	vi xs, ys;
	
	cin >> n;
	rep(i, n) cin >> x[i] >> y[i];
	cin >> m;
	rep(i, m){
		cin >> sx[i] >> sy[i];
		xs.pb(sx[i]);
		ys.pb(sy[i]);
	}
	sort(all(xs));
	xs.erase(unique(all(xs)), xs.end());
	sort(all(ys));
	ys.erase(unique(all(ys)), ys.end());
	
	g.resize(n);
	
	rep(i, m){
		int x = lower_bound(all(xs), sx[i]) - xs.begin();
		int y = lower_bound(all(ys), sy[i]) - ys.begin();
		
		s[x / 4000][y / 4000].pb(i);
	}
	
	rep(i, n){
		int xi = lower_bound(all(xs), x[i]) - xs.begin();
		int yi = lower_bound(all(ys), y[i]) - ys.begin();
		ll d = (1ull << 63) - 1;
		
		xi /= 4000;
		yi /= 4000;
		for(int j = xi - 1; j < xi + 2; j++) for(int k = yi - 1; k < yi + 2; k++){
			if(j < 0 || j >= xs.size()) continue;
			if(k < 0 || k >= ys.size()) continue;
			
			rep(l, s[j][k].size()){
				int xx = sx[s[j][k][l]], yy = sy[s[j][k][l]];
				d = min(d, dist(xx - x[i], yy - y[i]));
			}
		}
		rep(j, n) if(dist(x[i] - x[j], y[i] - y[j]) < d) g[i].pb(j);
	}
	
	vector<vi> scc;
	stronglyConnectedComponents(g, scc);
	vi to(n);
	vi in(scc.size());
	vector<vi> e(scc.size());
	
	rep(i, scc.size()) rep(j, scc[i].size()) to[scc[i][j]] = i;
	rep(i, n) rep(j, g[i].size()){
		int a = to[i], b = to[g[i][j]];
		if(a != b){
			e[a].pb(b);
			in[b]++;
		}
	}
	
	int ans = 0;
	rep(i, scc.size()) if(in[i] == 0) ans++;
	cout << ans << endl;
	
	return 0;
}