题意

题目描述

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

输入输出格式

输入格式：

第一行：(n)；(2leq nleq 200000)

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

1.0000

说明

(0leq x,yleq 10^9)

思路

利用分治的方法实现。我们先把所有点按照横坐标排序，然后查询每一个区间的最近点对距离。假设当前查询的是([l,r])区间的最近点对距离，那么这个区间的答案就在([l,mid])区间的最近点对距离、([mid+1,r])区间的最近点对距离、靠近中间的分别在两个区间中的一些点之间的距离中产生，我们主要考虑第三部分答案如何统计。

首先通过分治，我们已经求出了左右两区间的最近点对距离(min)，接下来找到([l,r])区间内横坐标与(mid)的横坐标相差不超过(min)的点，并将这些点两两匹配求出最近距离。这样能保证答案的正确性，但是时间复杂度呢？据说这样子做的时间复杂度是(O(nlog n))的，所以也不用担心超时的问题。

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct Point
{
    double x,y;
    bool operator < (const Point &sjf){return x<sjf.x;}
}p[200005],q[200005];
double devide(int l,int r)
{
    if(l==r) return DBL_MAX;
    else if(l+1==r) return sqrt((p[l].x-p[r].x)*(p[l].x-p[r].x)+(p[l].y-p[r].y)*(p[l].y-p[r].y));
    int mid=(l+r)>>1,cnt=0;
    double d=min(devide(l,mid),devide(mid+1,r));
    for(int i=l;i<=r;i++) if(fabs(p[i].x-p[mid].x)<=d) q[++cnt]=p[i];
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt&&fabs(q[i].x-q[j].x)<=d;j++)
            d=min(d,sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y)));
    return d;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    sort(p+1,p+n+1);
    printf("%.4f",devide(1,n));
    return 0;
}