2020牛客暑期多校训练营（第二场）Boundary

题目描述

一个很容易想到的思路：
枚举两个点，算圆心，再枚举有几个点在圆上。
明显超时。
然后想了想，发现枚举两个点，把每个圆心坐标出现次数存起来，
最大值+1就是ans
代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef long double ld;
typedef pair<ld,ld>P;
P yx(ld x1,ld y1,ld x2,ld y2,ld x3,ld y3)
{
	return P((((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)))),(((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<P,int>mp;
ld a[2005],b[2005];
int main()
{
	int n,ans=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) cin>>a[i]>>b[i];
	for (int i=1;i<=n;i++)
	 {
	 	mp.clear();
	 	for (int j=i+1;j<=n;j++)
	 	{
	 		if (a[i]*b[j]-a[j]*b[i]==0) continue;
	 		P p=yx(0,0,a[i],b[i],a[j],b[j]);
	 		mp[p]++;
	 		ans=max(ans,(int)mp[p]);
		 }
	 }
	cout<<ans+1<<endl;
}