AOJ 0090 Overlaps of Seals

問題の内容

10*10の正方形上に半径1の円をn個(n<=100)配置する。
最も多くの円の内部に含まれる正方形上の点はいくつの円に含まれるか。
（円の内部とは円周上も含む。）

解法

想定解法では任意の二つの円についてその交点を求め
いくつの円に含まれるかを数えるらしい。

AOJ : 0090 - Overlaps of Seals - Respect2Dの日記
AOJ Problem 0090 : Overlaps of Seals - kyuridenamidaのチラ裏
AOJ 0090: Overlaps of Seals：Snowing day：So-net blog

嘘解法

正方形上の点をできるだけ多く列挙して
その一つ一つについていくつの円に含まれるかを調べる。
円に含まれるかどうかの判定を甘くすると通った。

ソース

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
double x[100],y[100];
int main(){
    int n;
    while(1){
        scanf("%d",&n);
        if(n==0)    break;
        for(int i=0;i<n;i++)
            scanf("%lf,%lf\n",&x[i],&y[i]);
        int ans=0;
        for(double a=0;a<=10.1;a+=0.01)
            for(double b=0;b<=10.1;b+=0.01){
                int t=0;
                for(int i=0;i<n;i++)
                    if((a-x[i])*(a-x[i])+(b-y[i])*(b-y[i])<=1.001)
                        t++;
                ans=max(ans,t);
            }
        printf("%d\n",ans);
    }
    return 0;
}