题目描述
给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的
输入输出格式
输入格式：
第一行：n；2≤n≤200000
接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。
输出格式：
仅一行，一个实数，表示最短距离，精确到小数点后面4位。
输入输出样例
输入样例#1：
3 1 1 1 2 2 2
输出样例#1：
1.0000
看到网上很多点分治或kdtree的题解，我感觉人生很迷茫
这道题——就凭数学直觉，难道答案中的两个点，不该是纵坐标之差在所有点对中最小或者横坐标的差吗（欢迎神犇举出反例，相互学习，我这样说的原因是我AC了）
初始化：把答案设为极大值
首先我们把所有点按照x的大小排序，然后询问相邻点的距离，更新答案
然后我们把所有点按照y的大小排序，继续询问相邻点的距离，更新答案
然后答案就出来了。。
送上AC代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 template<class T>inline void read(T &_a) 6 { 7 char _ch=getchar();_a=0; 8 while(_ch<'0'||_ch>'9')_ch=getchar(); 9 while(_ch>='0'&&_ch<='9'){_a=(_a<<3)+(_a<<1)+_ch-'0';_ch=getchar();} 10 } 11 12 const int maxn=200001; 13 struct fff 14 { 15 int x,y; 16 inline bool operator < (const fff xx) const {return x<xx.x;} 17 }node[maxn]; 18 int n; 19 double ans=2000000000; 20 21 double calc(int x1,int y1,int x2,int y2) 22 { 23 return sqrt(pow((double)(x1-x2),2)+pow((double)(y1-y2),2)); 24 } 25 26 inline bool cmp(fff a,fff b) 27 { 28 return a.y<b.y; 29 } 30 31 int main() 32 { 33 read(n); 34 for (register int i=1;i<=n;++i) read(node[i].x),read(node[i].y); 35 sort(node+1,node+n+1); 36 for (register int i=1;i<n;++i) 37 ans=min(ans,calc(node[i].x,node[i].y,node[i+1].x,node[i+1].y)); 38 sort(node+1,node+n+1,cmp); 39 for (register int i=1;i<n;++i) 40 ans=min(ans,calc(node[i].x,node[i].y,node[i+1].x,node[i+1].y)); 41 printf("%.4lf",ans); 42 return 0; 43 }