AOJ : 0090 - Overlaps of Seals

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0090&lang=jp
日本語なので省略です

アルゴリズム

max=1, で初期化.(1枚でも重なっていると考えるため)
二重ループで, 任意の二つの円を選びます.
この二つの円の交点を求め, これらの交点を内包する円をカウントします(二重ループで選んだ二つの円は除く).
このカウント数+2がmaxより大きければ更新.

プログラム

#include <iostream>
#include <complex>
#include <vector>
using namespace std;

#define EPS (1e-5)

typedef complex<double> P;

vector<P> crossPoint(P a,P b){
  vector<P> res;

  if(abs(abs(b-a) - 2.0) < EPS){
    P c = a + b;
    res.push_back( P(c.real()/2,c.imag()/2) );
  }
  else if(abs(b-a) < 2.0){
    //円と円の交点計算
    P ab = b - a; //AからBへのベクトル
    P center = a + P(ab.real()/2,ab.imag()/2); //ABの中点へのベクトル
    P un1 = (ab * P(0, +1)) / abs(ab); //abの法線ベクトル1
    P un2 = (ab * P(0, -1)) / abs(ab); //abの法線ベクトル2
    double dist = sqrt(1 - pow(abs(ab) / 2, 2)); //ABの中点から円の交点までの距離
    P c1 = center + un1 * dist; //円の交点へのベクトル1
    P c2 = center + un2 * dist; //円の交点へのベクトル2

    res.push_back(c1);
    res.push_back(c2);
  }

  return res;
}

int main(void){
  int n;

  while(cin>>n,n){
    P p[n];
    for(int i=0;i<n;i++){
      double x,y;
      char ch;
      cin>>x>>ch>>y;
      p[i] = P(x,y);
    }

    int ans = 1;
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
        vector<P> v = crossPoint(p[i],p[j]);
        if(v.empty()) continue;
        int countA = 2;
        int countB = 2;
        for(int k=0;k<n;k++){
          if(i == k || j == k) continue;
          if(abs(v[0]-p[k]) - 1.0 < EPS) countA++;
          if(v.size() == 2 && abs(v[1]-p[k]) - 1.0 < EPS) countB++;
        }
        ans = max(ans,max(countA,countB));
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}