P6247

AIskeleton · 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));
}