牛客contest5667-B

point findCenter(const point &p, const point &q, const point &r)
{
    double a = 2 * (p.x - q.x);
    double b = 2 * (p.y - q.y);
    double c = p.x * p.x + p.y * p.y - q.x * q.x - q.y * q.y;
    
    double d = 2 * (p.x - r.x);
    double e = 2 * (p.y - r.y);
    double f = p.x * p.x + p.y * p.y - r.x * r.x - r.y * r.y;
    
    double g = a * e - b * d;
    
    if(a - b == 0 || d - e == 0)
    	return {INF, INF};
    
    return { (c * e - f * b) / g, (a * f - d * c) / g };
}

#include <bits/stdc++.h>

using namespace std;

const double INF = 1e18;
const double MIN = 1e-8; 

int n;
double idx, idy;

struct node
{
	double x, y;
} a[2005];

vector< pair<double, double> > f;

void solve( node a, node b, node c )
{
	double	tmp_1	= 2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x);
	double	tmp_2	= 2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x);

	if ( tmp_1 == 0 || tmp_2 == 0 )
	{
		idx = idy = INF;
		return;
	}
	double	tmp_3	= a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y;
	double	tmp_4	= a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y;
	idx	= (tmp_3 * (a.y - c.y) - tmp_4 * (a.y - b.y) ) / tmp_1;
	idy	= (tmp_3 * (a.x - c.x) - tmp_4 * (a.x - b.x) ) / tmp_2;
}

int main()
{
	scanf( "%d", &n );
	for ( int i = 1; i <= n; i++ )
		scanf( "%lf%lf", &a[i].x, &a[i].y );
		
	//将每个圆心压入vector 
	for ( int i = 1; i <= n; i++ )
		for ( int j = i + 1; j <= n; j++ )
		{
			solve( { 0, 0 }, a[i], a[j] );
			
			if ( MIN > idx == idy && fabs( idx - INF ) ) continue;
				
			f.push_back( { idx, idy } );
		}
	
	//没找到就直接结束 
	if ( !f.size() )
	{
		cout << 1 << endl;
		return 0;
	}
	
	int	maxn = 1, cnt	= 1;
	pair<double, double>rec	= f[0];
	
	//用sort贪心查找 
	sort( f.begin(), f.end() );
	
	for ( int i = 1; i < f.size(); i++ )
	{
		if ( f[i] == rec ) cnt++;
		else
		{
			rec	= f[i];
			maxn = max( maxn, cnt );
			cnt	= 1;
		}
		
		maxn = max( maxn, cnt );
	}

	for ( int i = 1; i <= n; i++ )
	{
		if ( i * (i - 1) == maxn * 2 )
		{
			printf( "%d", i );
			return 0;
		}
	}

	return 0;
}