B题Boundary

题目理解

给定n个点，然后一个坐标原点，要求一个过原点的圆经过最多的给定的点，输出最多的个数

解题思路

先枚举每个点，然后再枚举其他的点，通过两条中垂线，求出圆心坐标，最后取众数

代码

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
using namespace std;
typedef long double ld;
typedef pair<ld,ld> P;
P p[2010];
map<P,int> m;
P solve(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)))));//求出圆心坐标
}
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin>>p[i].first>>p[i].second;
	}
	for(int i=0;i<n;i++){
		m.clear();
		for(int j=i+1;j<n;j++){
			if(p[i].first*p[j].second-p[i].second*p[j].first==0) continue;
			P res=solve(0,0,p[i].first,p[i].second,p[j].first,p[j].second);
			m[res]++;
			ans=max(ans,m[res]);
		}
	}
	cout << ans+1;
	return 0;
}