AOJ 0090 - Overlaps of Seals

Volume 0がついに残り1問(Blur)．

解法

円が重なっている各部分に対して，それを構成する2円の交点は少なくとも1つは含まれる．

なぜなら，円が重なっている部分とそれを含む新たな円との共通部分を考えたとき，重なりを構成する円で，新たな円と交わる円が存在するからである．
よって，すべての2円の組に対し，交点を求め，その点に何個の円があるかを求めればいい．

2円A，Bの交点Pは次のようにして求められる．(注: 円A，円Bの半径はどちらも1である．)
(1) 線分ABの中点Mを求める．
(2) ABに垂直でMを通る直線上にあり，を満たす点Pを求める．

もう一方の点Qは点Pから求められる．

円が1つだけのときは"1"と出力することに注意しましょう．Ω＼ζ°)ﾁｰﾝ

コード

載せ忘れてた．自作の幾何ライブラリのようなものは長いので省略しています．

#include <cstdio>
#include <cmath>
#include <vector>

const double EPS = 1e-9, D_THETA = 0.06, D_R = 0.06;

int N;
P ps[100];
std::vector<P> is;

void addIntersection(int i, int j){
    if(dist(ps[i]-ps[j]) > 2.0){return;}
    
    P m{(real(ps[j])-real(ps[i])) / 2, (imag(ps[j])-imag(ps[i])) / 2}, n{-imag(m), real(m)};
    {
        double d = dist(n);
        n.real(real(n) / d);
        n.imag(imag(n) / d);
    }

    double t = std::sqrt(1 - norm(m));
    for(int k=-1;k<=1;k+=2){
        P p{t * k * real(n), t * k * imag(n)};
        P q = ps[i] + m + p;
        // printf("%.6f, %.6f\n", real(q), imag(q));
        is.push_back(q);
    }
}

int count(P p){
    int res = 0;
    for(int i=0;i<N;i++){
        if(dist(ps[i]-p) < 1.0 + EPS){res++;}
    }
    return res;
}

int main(){
    while(scanf("%d", &N), N){
        is.clear();
        
        for(int i=0;i<N;i++){
            double x, y;
            scanf("%lf,%lf", &x, &y);

            ps[i].real(x);
            ps[i].imag(y);
        }

        for(int i=0;i<N;i++){
            for(int j=i+1;j<N;j++){
                addIntersection(i, j);
            }
        }
        
        int res = 1;
        for(auto i : is){
            res = std::max(res, count(i));
        }

        printf("%d\n", res);
    }
}