Problem 1023 : Amazing Graze

Problem E: Amazing Graze
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1023&lang=jp

• 問題概要

円が２種類あって、ある種類の円に一定範囲内にあるもう一種類の円の数の総和を求めよ。

• 解法

円が多いのでｎの二乗は無理。
座標をその一定範囲くらいに分けて、同じエリアのものだけ探索する。
ただし、端っこのほうにその円がある可能性もあるので、そのエリア周辺の８方向も探索する。

そうすることで、比較する円の数を減らすことができる

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int T = 250;
const int dx[] = {0, 0, 1, 0, -1, 1, 1, -1, -1},
          dy[] = {0, -1, 0, 1, 0, -1, 1, 1, -1};

class Point{
public:
  int x, y;
  inline bool IN( const Point &p, const int &R){
    int norm = abs(x - p.x) * abs(x - p.x) + abs(y - p.y) * abs(y - p.y);
    return norm <= R;
  }
};

vector<Point> t[T][T];
main(){

  int N, M, R;
  while(1){
    scanf("%d %d %d", &N, &M, &R);
    if( N + M == 0)break;  
    int sum = 0;
    R = 16 * R * R;
    rep(i, T)rep(j, T)t[i][j].clear();
    Point P[N];
    rep(i, N){
      scanf("%d %d", &P[i].x, &P[i].y);
    }
    rep(i, M){ 
      Point p; 
      scanf("%d %d", &p.x, &p.y);
      t[p.y / 40][p.x / 40].push_back(p);
    }
    rep(i, N){
      rep(j, 9){
	int nx = P[i].x/40 + dx[j];
	int ny = P[i].y/40 + dy[j];
	if(nx < 0 || ny < 0 || nx >= T || ny >= T)continue;
	FOR(it, t[ny][nx]){
	  if(P[i].IN(*it, R))sum++;
	}
      }
    } 
    cout << sum << endl;
  }
}