数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：求两点间的最短距离
假设我们有一组坐标，每个元素的形式为 [x, y]，表示欧几里得坐标。我们必须找到任何两个给定坐标之间最小的平方距离 (x1 - x2) 2 + (y1 - y2) 2。
因此，如果输入类似于 coordinates = {{1, 2},{1, 4},{3, 5}}，则输出将为 4。
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 ytorightmostx
对数组 coordinates 进行排序
ret := 无穷大
对于 coordinates 中的每个 p：
it = 返回 ytorightmostx 中 (p[1] - sqrt(ret)) 的值，或 ytorightmostx 中大于它的最小值
当 it 不等于 ytorightmostx 的最后一个元素时：
yd := it 的第一个值 - p[1]
如果 yd > 0 且 yd * yd >= ret，则：
退出循环
nxt = it
将 nxt 加 1
ret := min(ret, dist(p[0], p[1], it 的第一个值, it 的第二个值))
xd := it 的第二个值 - p[0]
如果 xd * xd >= ret，则：
从 ytorightmostx 中删除 it
it := nxt
ytorightmostx[p[1]] := p[0]
返回 ret
定义一个函数 dist()，它将接收 xl, yl, xr, yr。
xd := xl - xr
yd := yl - yr
返回 xd * xd + yd * yd
示例
让我们看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
long long dist(long long xl, long long yl, long long xr, long long yr) {
long long xd = xl - xr;
long long yd = yl - yr;
return xd * xd + yd * yd;
}
int solve(vector<vector<int>>& coordinates) {
map<long long, long long> ytorightmostx;
sort(coordinates.begin(), coordinates.end());
long long ret = 1e18;
for (auto& p : coordinates) {
auto it = ytorightmostx.lower_bound(p[1] - sqrt(ret));
while (it != ytorightmostx.end()) {
long long yd = it->first - p[1];
if (yd > 0 && yd * yd >= ret) {
break;
}
auto nxt = it;
nxt++;
ret = min(ret, dist(p[0], p[1], it->second, it->first));
long long xd = (it->second - p[0]);
if (xd * xd >= ret) {
ytorightmostx.erase(it);
}
it = nxt;
}
ytorightmostx[p[1]] = p[0];
}
return ret;
}
int main(){
vector<vector<int>> coord = {{1, 2},{1, 4},{3, 5}};
cout << solve(coord) << endl;
return 0;
}输入
{{1, 2},{1, 4},{3, 5}}输出
4
更新于：2020-12-23
1K+ 次浏览
广告