読者です 読者をやめる 読者になる 読者になる

AOJ0090 Overlaps of Seals

解法
2円の交点を全て求めて、交点の集合を得る。その交点それぞれがどの円に含まれるかを全て調べ、含む円の数をカウントし最大値を求めれば良い。
2円の交点を求める際、complex の polar が便利。polar(r, θ) で、対応する複素平面における座標が求まる。

#include <iostream>
#include <cmath>
#include <vector>
#include <complex>
#include <cstdio>
 
using namespace std;
 
typedef complex<double> P;
 
#define EPS (1e-8)
 
int main() {
  int n;
  while(cin >> n && n) {
    vector<P> c;
    for(int i=0; i<n; i++) {
      double x, y;
      scanf("%lf,%lf", &x, &y);
      c.push_back(P(x, y));
    }
     
    vector<P> p;
    for(int i=0; i<n-1; i++) {
      for(int j=i+1; j<n; j++) {
        if(norm(c[i]-c[j]) <= 4.0 + EPS) {
          P cent = (c[i]+c[j]) / 2.0;
          double len = sqrt(1.0 - norm(c[i]-cent));
          double ang = arg(c[i]-c[j]);
          P p1 = cent + polar(len, ang + M_PI/2);
          P p2 = cent + polar(len, ang - M_PI/2);
          p.push_back(p1);
          p.push_back(p2);
        }
      }
    }
     
    int const N = p.size();
    int res = 1;
    for(int i=0; i<N; i++) {
      int cnt = 0;
      for(int j=0; j<n; j++)
        if(norm(p[i]-c[j]) <= 1.0 + EPS) { cnt ++; }
      res = max(res, cnt);
    }
     
    cout << res << endl;
  }
   
  return 0;
}