题目

{% fold 点击显/隐题目 %}

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

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

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

3 1 1 1 2 2 2

1.0000

{% endfold %}

题解

正确思路好像要用主席树,然而不会,只能暴力写一发

首先可以知道如果按照 (x,y) 排序,可以发现离得近的点普遍距离较近
存在反例,(1,1) (1,100) (2,1) 排序后显然第一个和第三个距离更近

但是在已经范围内我们可以近似认为没影响(比较的时候多比较几组就行了~)

那么我们尝试采用二分进行优化
用 dfs(l,r) 来表示 [l,r) 的最近的两个点的距离

显然有:

最近的两个点可能全部在 mid 左侧的范围里,也即 dfs(l,mid)
最近的两个点可能全部在 mid 右侧的范围里,也即 dfs(mid,r)
最近的两个点一个在 mid 左侧,一个在 mid 右侧

前两种情况都比较容易解决,只需要考虑最后一种情况
遍历两侧的所有点,计算他们的距离最小值

根据最上面的说明,可以得知横跨 mid 左右的距离最近的点必然距离 mid 距离不远
可以将 x1-x2 近似看成距离,如果它已经大于之前已经获得最小距离,可以直接结束循环
(存在极端情况导致答案错误)

另外,根据两点间距离公式 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
可以发现有一个非常浪费时间的 sqrt() 需要多次运算,可以在前面比较的时候直接比较距离的平方
只要在最后输出的时候求一下平方就行
(需要注意,如果这里比较距离的平方,上面遍历需要比较 (x1-x2)^2)

代码

{% fold 点击显/隐代码 %}```cpp 平面上最近点对 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
///
#define debug
#include
///
#include
#include

#include
#include
#include
using namespace std;

const int maxn = 60005;
const double INF = 9e9;
const int K = 5;

struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator<(const Point &rhs) const { return x < rhs.x; }
};
Point point[maxn];

inline double pow(double a, double n) {
if (n == 0)
return 1.0;
if (n == 1)
return a;
return pow(a, n / 2) * pow(a, n - n / 2);
}

inline double dis(Point a, Point b) {
return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}

//[l,r)
double dfs(int l, int r) {
int mid = (l + r) / 2;

if (r - l < 2) {
    return INF;
}
if (r - l == 2) {
    return dis(point[l], point[l + 1]);
}

double mm = min(dfs(l, mid), dfs(mid, r));

for (int i = mid - 1; i >= l && pow(point[mid].x - point[i].x,2) < mm; i--)
    for (int j = mid; j < r && pow(point[r].x - point[mid-1].x,2) < mm; j++)
        mm = min(mm, dis(point[i], point[j]));

return mm;

}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
    scanf("%d%d", &point[i].x, &point[i].y);

sort(point, point + n);
printf("%.4f\n", sqrt(dfs(0, n)));

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}

AOJ 862.平面上最近点对

题目

题解

代码