Codeforces #33 D "Knights"

問題：http://codeforces.com/contest/33/problem/D

プラクティス．
各点を中に持つ円を計算しておいて，ある点からある点に行くときはそれぞれの点だけを中に持つ円の数を数えれば良い．
これはTopcoderか何かで似たような問題があった気がするので本番で取り組んだけど，片方の点だけを中に持つ円を見つける部分がおかしかったようでテストケース８でWA．

import java.util.*;

public class D_Knights {
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt(),m=s.nextInt(),k=s.nextInt();
        int[][]loc=new int[n][2];
        for(int i=0;i<n;++i){
            loc[i][0]=s.nextInt();
            loc[i][1]=s.nextInt();
        }
        boolean[][]in=new boolean[n][m];
        for(int i=0;i<m;++i){
            int r=s.nextInt(),cx=s.nextInt(),cy=s.nextInt();
            for(int j=0;j<n;++j){
                if(Math.pow(r,2)>Math.pow(loc[j][0]-cx,2)+Math.pow(loc[j][1]-cy,2)){
                    in[j][i]=true;
                }
            }
        }

        for(;k-->0;){
            int a=s.nextInt()-1,b=s.nextInt()-1;
            int sum=0;
            for(int i=0;i<m;++i){
                sum+=in[a][i]^in[b][i]?1:0;
            }
            System.out.println(sum);
        }
    }
}

本番に提出したソース（テストケース８でWA）

import java.io.*;
import java.math.*;
import java.util.*;
import static java.lang.Math.*;

public class D {
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt(),m=s.nextInt(),k=s.nextInt();
        int[][]loc=new int[n][2];
        for(int i=0;i<n;++i){
            loc[i][0]=s.nextInt();
            loc[i][1]=s.nextInt();
        }
        int[][]circles=new int[m][3];
        for(int i=0;i<m;++i){
            circles[i][2]=s.nextInt();
            circles[i][0]=s.nextInt();
            circles[i][1]=s.nextInt();
        }

        List<Set<Integer>>list=new ArrayList<Set<Integer>>();
        for(int i=0;i<n;++i){
            Set<Integer>li=new HashSet<Integer>();
            for(int j=0;j<m;++j){
                BigInteger r2=BigInteger.valueOf(circles[j][2]).pow(2);
                BigInteger dx=BigInteger.valueOf(loc[i][0]-circles[j][0]).pow(2);
                BigInteger dy=BigInteger.valueOf(loc[i][1]-circles[j][1]).pow(2);
                if(r2.compareTo(dx.add(dy))>=0){
                    li.add(j);
                }
            }
            list.add(li);
        }
        int[][]c=new int[n][n];
        for(int i=0;i<n;++i){
            Set<Integer>aset=list.get(i);
            c[i][i]=aset.size();
            for(int j=i+1;j<n;++j){
                Set<Integer>bset=list.get(j);
                Set<Integer>cset=new HashSet<Integer>();
                for(int be:bset){
                    if(aset.contains(be)){
                        cset.add(be);
                    }
                }
                c[i][j]=c[j][i]=cset.size()*2;
            }
        }
        for(;k-->0;){
            int a=s.nextInt()-1,b=s.nextInt()-1;
            System.out.println(c[a][a]+c[b][b]-c[a][b]);
        }
    }
}