ICPC 国内予選2004D Circle and Points AOJ1132

解法：

• 任意の二点を選ぶ(N*N通り）

• その二点が円周上にくるような半径１の円の中心の座標を求める。（二点間の距離が２以上の時はそのような円は存在しないのでスキップ）

• その円にいくつの点が含まれているか計算量Nで求める。その最大値が答え。

計算量O(N^3)

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

double p[305][2];
int n;

double dist(int a,int b){
    return sqrt((p[a][0]-p[b][0])*(p[a][0]-p[b][0])+(p[a][1]-p[b][1])*(p[a][1]-p[b][1]));
}

double get_o(int i,double st,double en,double th,double b){
    double diff = 1.0;
    while(diff > 0.00001){
        double half[2];
        half[0] = (en+st)/2.0;
        half[1] = th*half[0] + b;
        if( (p[i][0]-half[0])*(p[i][0]-half[0]) + (p[i][1]-half[1])*(p[i][1]-half[1]) >1){
            en = half[0];
        }else{
            st = half[0];
        }
        diff = en - st;
        if(diff < 0 ) diff = -1.0 * diff;
    }
  //  cout << "st:" << st << ", en:" << en << endl;
    return st;
}

int find_ans(double x,double y,int a,int b){
    int ans = 2;
    for(int i = 0;i < n;i++){
        if(i == a || i == b)continue;
        if( (p[i][0]-x)*(p[i][0]-x) + (p[i][1]-y)*(p[i][1]-y) <= 1.0) ans++;
    }
    return ans;
}

int main(){
    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i < n;i++){
            cin >> p[i][0] >> p[i][1];
        }
        int ans = 1;
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                double d = dist(i,j);
                if(d > 2.0)continue;
                if(true){
            //    if(p[i][1] != p[j][1]){
                    double th = -(p[j][0]-p[i][0])/(p[j][1]-p[i][1]);
                    double half[2];
                    half[0] = (p[i][0]+p[j][0])/2.0;
                    half[1] = (p[i][1]+p[j][1])/2.0;
                    double b = half[1] - th*half[0];
                    double o[2];
                    o[0] = get_o(i,half[0],half[0]+1,th,b);
                    o[1] = th*o[0] + b;
                //    cout << "x1:" << p[i][0] << ",y1" << p[i][1] << ",x2" << p[j][0] << ",y2" << p[j][1] << ",ox" << o[0] << ",oy" << o[1] << endl;
                    ans = max(ans,find_ans(o[0],o[1],i,j));
                    o[0] = get_o(i,half[0],half[0]-1,th,b);
                    o[1] = th*o[0] + b;
                //    cout << "x1:" << p[i][0] << ",y1" << p[i][1] << ",x2" << p[j][0] << ",y2" << p[j][1] << ",ox" << o[0] << ",oy" << o[1] << endl;
                    ans = max(ans,find_ans(o[0],o[1],i,j));
                }
            }
        }
        cout << ans << endl;
    }
}