题目描述

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入输出格式

输入格式：

第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式：

仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例

输入样例#1：

3

1 1

1 2

2 2

输出样例#1：

1.0000

说明

0<=x,y<=10^9

---

题解

这是一道分治。

首先，暴力枚举点对计算是n^2，肯定超。

然后数据范围200000，就肯定是nlogn的算法，然后我就想到二分答案，也进行了实现，然后，就没有然后了。。。

于是我就愉快地看了题解，发现确实是二分，可是只是二分区间，然后再合并，就像归并排序。

忽然发现很有道理，因为，点对是两个点，然后就可以分治地去找到满足条件的点对，并更新答案了。

然后，我就写了一遍，还是很好写的，真的很像归并排序求逆序对。

然后我就交了一次：

---

---

结果60，我就当场懵逼。。

然后回去看题解，发现他写了实数读入优化，我就copy过来，想着试一试，又交了一次，然后：

---

---

wtf，这都行？？？

还有，为什么还是有一个WA？

于是我就开始看我和他的程序有什么区别，发现排序的函数，他多判了一种x相等时比较y，我就加上了，然后重新交了一次：

---

---

还有这种操作？？？

这么差下来，就是60-100的差距呀，这一般都是算法差距呀。。。。。。。

我只能说，这题太阴险了。。

你们自己可以去体会体会。

---

至于这题算法具体描述，我懒得自己写了，copy一段（来自@xzyxzy）：

于是——怎么分

✔将各个点（结构体）按x的从小到大排序

✔首先运用二分思想将点集合分到最后只剩两个点的时候

✔然后用这两点之间的距离更新答案（答案初始化为无限大）

✔然后我们要找到二分的具体实现方案——每次分到一些点时，找到这些点标号的中间（因为点都排好序了，所以其实也就是找到x轴上一条分界线），将整个点的集合大致均分为两个部分

✔在分界线的右侧，将与分界线的距离小于ans的点纳入到一个辅助结构体里面

✔在分界线的左侧，不断枚举点，枚举到离分界线小于ans的点时，与辅助结构体中的点挨个（等会有解释）判断其距离有没有小于ans，更新ans

注意下用double别掉了精度，然后格式化输出就好了

然后我的代码中，为了避免超时，还是很努力地自己写了个实数的输入优化没想到也过了

---

最后，贴一下代码：

#include
     
      #define ll long long#define inf 0x3f3f3f3fusing namespace std;const double eps=0.0001;double read(){    char ch=getchar();    while(ch!='.'&&(ch>'9'||ch<'0')) ch=getchar();    int h=0,t=1,b=0;    while(ch!='.'&&ch<='9'&&ch>='0')    {        h=h*10+ch-48;        ch=getchar();    }    if(ch=='.')    {        ch=getchar();        while(ch<='9'&&ch>='0')        {            b=b*10+ch-48;            ch=getchar();            t*=10;        }    }    return h+(b*1.000000000)/t;}struct point{    double x,y;    bool operator < (const point& b) const {        return x==b.x?y
      
       
        =ans)continue;        while(t<=cnt&&fabs(g[t].y-p[i].y)
       
      
     

end