UVa12240 Cocircular Points

解法
テストケースが書いていないが、３点より特定した一つの円の周上に１点が乗っかるか調べる O(N^4) の解法で正答できるようになっている。

３点から一つの円を特定する方法は垂直二等分線の交点である。
２点のペアの中点と、その２点のペアのベクトルを90度回転させた時の点とを結ぶ直線を考えて、その２つの直線の交点を求める。

#include <cstdio>
#include <algorithm>
#include <complex>
#include <vector>
#include <numeric>

using namespace std;

#define X real()
#define Y imag()

#define SQ(x) ((x)*(x))

double const EPS = 1e-7;

typedef complex<double> P;

double dist2(P a, P b) {
  return SQ(a.X - b.X) + SQ(a.Y - b.Y);
}

double cross(P a, P b) {
  return a.X*b.Y - a.Y*b.X;
}

P getPointLL(P a1, P a2, P b1, P b2) {
  P a = a2 - a1, b = b2 - b1;
  return a1 + a*cross(b, b1-a1) / cross(b, a);
}

P getCenterOfCircle(P a, P b, P c) {
  P mab = (a+b)/2.;
  P mbc = (b+c)/2.;
  P vab = (b-a)*P(0,1), vbc = (c-b)*P(0,1);
  return getPointLL(mab, mab+vab, mbc, mbc+vbc);
}
int main() {
  
  int N;
  while(scanf("%d", &N) && N) {
    vector<P> in;
    for(int i=0; i<N; i++) {
      double x, y;
      scanf("%lf %lf", &x, &y);
      in.push_back(P(x, y));
    }
    
    int ans = 0;
    for(int i=0; i<N; i++)
      for(int j=i+1; j<N; j++)
        for(int k=j+1; k<N; k++) {
          P center = getCenterOfCircle(in[i], in[j], in[k]);
          double R2 = dist2(center, in[i]);
          int cnt = 0;
          for(int l=0; l<N; l++) {
            if(abs(dist2(in[l], center)-R2) < EPS) { cnt++; }
          }
          ans = max(ans, cnt);
        }
    
    printf("%d\n", max(ans, min(2, N)));
  }
  return 0;
}