資料結構
網路
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+ 次瀏覽
廣告