传送门

题目大意： 给出n个点，圆心和半径任意取的情况下，要求这n个点尽可能多的点出现在圆上。该圆一定经过坐标原点(0,0)。求满足要求的圆上至多有多少个点。

思路很清晰，三点确定一个圆，题目中又给死了一个点，那么O(n²)枚举剩下的两个点，把找到的圆心放在集合里，然后再去找出现次数最多的圆心枚举圆上点就可以了。

三点共圆圆心的寻找公式如下：

那么不难得到它的代码表达：

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;
}

其中去重的vector可以用unordered_set来做，有时间会再调。