AOJ - Problem 1023 : Amazing Graze

AOJ

AN個の戦闘機とBN個の敵弾があり、それぞれの戦闘機について距離が4*R以内にある敵弾を数える問題でした(距離は戦闘機の中心座標から敵弾の中心座標までの距離で計算)。

AN,BN <= 10^5なので各戦闘機についてすべての敵弾との距離を比較すると最大で10^10程度調べる必要があり間に合いません。そのためフィールドを40*40ごとの区画に分割します。
各戦闘機について自分のいる区画とその周囲8区画だけ調べるようにすると調べる数を減らすことができます。

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

int dx[9] = {-1,-1,-1,0,0,0,1,1,1};
int dy[9] = {-1,0,1,-1,0,1,-1,0,1};

int D(int x1, int y1, int x2, int y2 ){
	return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ;
}

int main(){
	int AN, BN, R;
	while( scanf("%d %d %d", &AN, &BN , &R ), AN || BN ){
		int AX[100001], AY[100001];
		vector<P> m[250][250];
		int ans=0;

		for(int i=0 ; i < AN ; i++ ){
			scanf("%d %d", &AX[i], &AY[i]);
		}
		for(int i=0 ; i < BN ; i++ ){
			int x, y;
			scanf("%d %d", &x, &y );
			P p(x,y);
			m[y/40][x/40].push_back( p );
		}
		for(int i=0 ; i < AN ; i++ ){
			int ax = AX[i];
			int ay = AY[i];

			for(int j=0 ; j < 9 ; j++ ){
				int mx = ax/40 + dx[j];
				int my = ay/40 + dy[j];
				if( mx < 0 || my < 0 || mx >= 250 || my >= 250 ) continue;
				vector<P> B = m[my][mx];
				for(int k=0 ; k < B.size() ; k++ ){
					int bx = B[k].first;
					int by = B[k].second;
					if( D(ax,ay,bx,by) <= 16*R*R ){
						ans++;
					}
				}
			}
		}
		printf("%d\n", ans );
	}
}