1023 - Amazing Graze

俺の妹（ｒｙも出てきたことなのでひさびさに更新。
※追記：これ消えないのか。

問題概要

平面内に半径Rの円がある。円には2タイプあり、タイプが異なる任意の2円について、その最短距離（円周上の点同士による距離）が2R以下であるような組を考える。それらはいくつあるだろうか。

コード

#include<cstdio>
#include<iostream>
#include<set>
#include<map>
using namespace std;
#define foreach(it,b,e) for(__typeof((b)) it=(b);it!=(e);++it)
#define foreachall(it,o) foreach(it,(o).begin(),(o).end())
int main(){
  while(true){
    int ans = 0;
    map<int, set<int> > Xa,Xb;
    int AN,BN,R;

    scanf("%d%d%d", &AN, &BN, &R);
    if( AN == 0 && BN == 0 ) break;

    for(int i=0;i<AN;++i){ int xa,ya; scanf("%d%d",&xa,&ya); Xa[xa].insert(ya); }
    for(int i=0;i<BN;++i){ int xb,yb; scanf("%d%d",&xb,&yb); Xb[xb].insert(yb); }
    
    foreachall(itxa,Xa){
      foreachall(itxas,itxa->second){
	int X=itxa->first, Y=*itxas;
	foreach(itm,Xb.lower_bound(X-4*R),Xb.upper_bound(X+4*R+1)){
	  foreach(its,itm->second.lower_bound(Y-4*R),itm->second.upper_bound(Y+4*R+1)){
	    int dx = X-itm->first, dy = Y-*its, d=dx*dx+dy*dy;
	    if( d <= 16*R*R ) ++ans;
	  }
	}
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

解法

ある円の中心(x,y)について、そこを中心とする一辺が8Rの正方形内にある円を調べる。ただし円の数が多いため、そこに含まれる円にアクセスする方法は特定のデータ構造に頼らなければならない。プログラムではmap・set・lower_bound・upper_boundを用いて実装した。