AOJ 862.平面上最近点对

287


题目



点击显/隐题目

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


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


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


3
1 1
1 2
2 2


1.0000




题解


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

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

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

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

显然有:
  1. 最近的两个点可能全部在 mid 左侧的范围里,也即 dfs(l,mid)
  2. 最近的两个点可能全部在 mid 右侧的范围里,也即 dfs(mid,r)
  3. 最近的两个点一个在 mid 左侧,一个在 mid 右侧

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

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

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

代码


点击显/隐代码
//*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <cmath>
#include <iostream>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论