自动搬运

查看原文

来自洛谷，原作者为

	AIskeleton _

搬运于2025-08-24 22:18:59，当前版本为作者最后更新于2022-03-16 10:49:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们充分发扬人类智慧：

将所有点按 $x$ 坐标排序。

根据数学直觉，在排序后，最近的两个点在数组中肯定不会离得太远，最远的两个点在数组中肯定不会离得太近。

所以只取每个点向后的 $3$ 个点更新最近距离，并取最后向前的 $13$ 个点更新最远距离。

这样速度快得飞起，直接拿到了此题的最优解。

#include<bits/stdc++.h>
using namespace std;
int s1=3,s2=13,n;
double mn=1e20,mx=0;
struct d{double x,y;}a[200005];
bool cmp(d X,d Y){return X.x<Y.x;}
double dis(int n,int m){return (a[n].x-a[m].x)*(a[n].x-a[m].x)+(a[n].y-a[m].y)*(a[n].y-a[m].y);}
int main(){
	cin>>n;for(int i=0;i<n;i++)
    	printf("%lf %lf",&a[i].x,&a[i].y);
    sort(a,a+n,cmp);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n&&j<i+s1;j++)	mn=min(mn,dis(i,j)); 
		for(int j=n-1;j>=i&&j>=n-s2;j--)	mx=max(mx,dis(i,j)); 
	}printf("%.2lf %.2lf",sqrt(mn),sqrt(mx));
}