Giả sử chúng ta có một danh sách các tọa độ trong đó mỗi phần tử có dạng [x, y], đại diện cho các tọa độ Euclide. Chúng ta phải tìm khoảng cách bình phương nhỏ nhất (x 1 - x 2 ) 2 + (y 1 - y 2 ) 2 giữa hai tọa độ được cung cấp bất kỳ.
Vì vậy, nếu đầu vào giống như tọa độ ={{1, 2}, {1, 4}, {3, 5}}, thì đầu ra sẽ là 4.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ ytorightmostx
-
sắp xếp tọa độ mảng
-
ret:=infinity
-
cho mỗi p trong sợi dây thừng -
-
it =trả về giá trị trong đó (p [1] - sqrt (ret)) nằm trong ytorightmostx hoặc giá trị nhỏ nhất lớn hơn nó từ ytorightmostx
-
trong khi nó không bằng phần tử cuối cùng của ytorightmostx, do -
-
yd:=first - p [1] trong số đó
-
nếu yd> 0 và yd * yd> =ret, thì -
-
Ra khỏi vòng lặp
-
-
nxt =it
-
tăng nxt lên 1
-
ret:=tối thiểu của (ret, dist (p [0], p [1], giá trị đầu tiên của nó, giá trị thứ hai của nó)
-
xd:=giá trị thứ hai của nó - p [0]
-
nếu xd * xd> =ret, thì -
-
xóa nó khỏi ytorightmostx
-
-
it:=nxt
-
-
ytorightmostx [p [1]]:=p [0]
-
-
trả lại ret
-
Xác định một hàm dist (), điều này sẽ lấy xl, yl, xr, yr.
-
xd:=xl - xr
-
yd:=yl - yr
-
trả về xd * xd + yd * yd
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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; }
Đầu vào
{{1, 2},{1, 4},{3, 5}}
Đầu ra
4