Boundary

题目描述

Given {n}n points in 2D plane. Considering all circles that the origin point {(0, 0)}(0,0) is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

输入

The first line contains one integer n~(1 \leq n \leq 2000)n (1≤n≤2000), denoting the number of given points.
Following {n}n lines each contains two integers x, y~(|x|,|y| \leq 10000)x,y (∣x∣,∣y∣≤10000), denoting a given point {(x, y)}(x,y).
It’s guaranteed that the points are pairwise different and no given point is the origin point.

输出

Only one line containing one integer, denoting the answer.

样例输入

4
1 1
0 2
2 0
2 2

样例输出

3

题目大意

给定平面上n个点，考虑所有原点(0,0)在边界上的圆，找出最多有几个点可以在同一个圆的边界上。输出数量。

分析

乍一看挺难，其实可以推公式。
用我们小学二年级学过的知识就知道三点确定一个圆，求出任意两条两点连线段的中垂线，求出交点坐标即可（方法很多，不一一列举了）。
说完推导过程，上公式：

已知圆上三点为(x1,y1),(x2,y2),(x3,y3)，设圆心坐标为(x,y),则:
x=((y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)-(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1))/(2.0*((x3-x1)*(y2-y1)-(x2-x1)*(y3-y1)));
y=((x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)-(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1))/(2.0*((y3-y1)*(x2-x1)-(y2-y1)*(x3-x1)));

解决了这个，剩下的就简单了~
枚举两个点与圆心确定一个圆，求出该圆圆心坐标后用一个map来统计相同圆心出现次数即可。
上代码：

#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define P pair<ld,ld>

using namespace std;

ld x[2020],y[2020];
map<P,int> mp;
int n,ans;

int main()
{
	scanf("%d",&n);for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)
	{
		mp.clear();
		for(int j=i+1;j<=n;j++)
		{
			if(x[i]*y[j]-x[j]*y[i]==0) continue;//若三点共线则不构成圆，具体推理略
			ld xx=((y[j]-y[i])*y[i]*y[j]-x[i]*x[i]*y[j]+x[j]*x[j]*y[i])/(x[j]*y[i]-x[i]*y[j]);
            ld yy=((x[j]-x[i])*x[i]*x[j]-y[i]*y[i]*x[j]+y[j]*y[j]*x[i])/(y[j]*x[i]-y[i]*x[j]);
            mp[P(xx,yy)]++;ans=max(ans,mp[P(xx,yy)]);
		}
	}
	printf("%d",ans+1);
}

------原创文章，仅供参考