题目描述

现在有一个收纳器，收纳器能够将位于以收纳器为圆心、设定长度为半径形成的圆的圆周上所有物品瞬间装进来。

为简化描述，将房间视为一个平面坐标系，房间里的物品是坐标系上的点。由于房间足够大，可以认为没有边界。

这张图中，收纳器位于$(0,0)$，设定半径为$2$，可以一次性将物品A、B、C装进去。

房间里有$N$个物品，AC狗手持收纳器，可以移动到任意位置，半径长度自主设定。现在他想知道使用一次超级收纳器最多可以将多少个物品装进来。

输入格式

输入的第一行为一个整数$N$，代表$N$个物品。

接下来$N$行每行两个数$X_i,Y_i$（最多包含小数点后五位），代表这个物品所处的坐标。

输出格式

输出为一个整数，代表最多可以同时收纳的物品数。

样例 #1

样例输入 #1

5
0 2
-2 0
2 0
1 1.73205
2 2

样例输出 #1

4

样例 #2

样例输入 #2

4
0 2
0 -2
-2 0
2 2

样例输出 #2

3

提示

【数据规模】

输入数据保证，不会出现重复的点。

对于10%的测试数据，$1<=N<=10$；$-100<=X_i,Y_i<=100$。所有点的横纵坐标均为整数，且收纳器放置的最佳位置在原点。

对于20%的测试数据，$1<=N<=20$；$-100<=X_i,Y_i<=100$。所有点的横纵坐标均不相同。

对于100%的数据，$1<=N<=150$；$-2^{30} <= X_i,Y_i <= 2^{30}$。没有额外限制。

【精度说明】

判断精度时仅精确到百分位，例如样例中的$(0,2)，(-2,0)，(1,1.73205)，(2,0)$均位于$X^2+Y^2 = 4$的圆周上。

其中$1×1+1.73205×1.73205=3.9999972025$，$3.9999972025$精确到百分位后是$4.00$，符合要求。

#include<bits/stdc++.h>
using namespace std;
#define double long double
const double N=0.06;//误差 
int n;
struct node{
	double x,y;
}a[155];
double g[155][155];//两点距离平方 
double cal(int i,int j){//两点距离的平方 
	return (a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
bool c(int A,int B,int C,int D){//托勒密定理变形（感觉精度不高） 
	double t=(g[A][B]*g[C][D]+g[A][D]*g[B][C]-g[A][C]*g[B][D]);
	if(fabs(t*t-4*g[A][B]*g[C][D]*g[A][D]*g[B][C])<=N) return true;
	return false;
}
bool c_l(int i,int j,int k){//判断是否三点共线，用2个斜率交叉相乘减小误差 
	double k1=(a[i].y-a[j].y)*(a[i].x-a[k].x);
	double k2=(a[i].y-a[k].y)*(a[i].x-a[j].x);
	if(fabs(k1-k2)<=N) return true;
	return false;
}
int main(){
	cin>>n;
	if(n<3){//小于3一定有n个 
		cout<<n<<endl;
		return 0;
	} 
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) g[i][j]=0;
			else {
				if(g[j][i]!=0) g[i][j]=g[j][i];
	            else g[i][j]=cal(i,j);
			}
		}
	}
	int ans=2;//计数 
	//逐个枚举 
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
		    for(int k=j+1;k<=n;k++){//用已知的3点，判断n点公圆 
		    	if(c_l(i,j,k)) continue; 
		    	int cnt=3; 
		    	for(int w=k+1;w<=n;w++){
		    		if(c(i,j,k,w)){
		    			cnt++;
					}
				}   
				ans=max(ans,cnt);
	        }
	    }
	}
	cout<<ans<<endl;
	return 0;
}

以上为40分代码，求助。 https://www.luogu.com.cn/problem/U278684