题目背景
P7883 平面最近点对（加强加强版）
题目描述
给定平面上 \(n\) 个点，找出其中的一对点的距离，使得在这 \(n\) 个点的所有点对中，该距离为所有点对中最小的
输入格式
第一行：\(n\) ，保证 \(2\le n\le 200000\) 。
接下来 \(n\) 行：每行两个实数：\(x\ y\) ，表示一个点的行坐标和列坐标，中间用一个空格隔开。
输出格式
仅一行，一个实数，表示最短距离，精确到小数点后面 \(4\) 位。
输入输出样例 #1
输入 #1
3
1 1
1 2
2 2
输出 #1
1.0000
说明/提示
数据保证 \(0\le x,y\le 10^9\)
基本思路
那我们先讲如何骗分好了，其实也不是骗分，可以直接过的。
先观察，我们要将点进行全部匹配的话会到达 \(O(n^2)\) 的复杂度，但仔细想想，我们真的要匹配那么多吗？是不是将点按坐标排好序后附近应该只有不多的点是进入射程的，只不过我们不知道如何对所谓“附近”的点进行再次的判断罢了。
但是等一下，既然说是附近，那我们要不就直接模糊化处理，我们就直接对它在数组中附近的五个点进行计算比较不就可以了？
原作：
于是就有：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct node{double x,y;
}a[N];
int n;
double ans;
bool cmp(node nx,node ny){if(nx.x!=ny.x) return nx.x<ny.x;return nx.y<ny.y;
}
double found(double t){//二分开方double l=0,r=t,mid;while(r-l>=0.000001){mid=(l+r)/2.0;if((mid*mid)>t) r=mid;else l=mid;}return l;
}
double getnum(node nx,node ny){double xx=nx.x-ny.x,yy=nx.y-ny.y,sum;xx*=xx;yy*=yy;sum=xx+yy;return found(sum);
}
int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}ans=std::numeric_limits<double>::max();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){for(int j=i+1;j<=(i+8)&&j<=n;j++){ans=min(ans,getnum(a[i],a[j]));}}printf("%.4f",ans); return 0;
}