Giả sử ta có danh sách tọa độ mỗi phần tử dạng [x, y], đại diện cho tọa độ Euclid. Ta phải tìm khoảng cách bình phương nhỏ nhất (x1-x2)^2 + (y1-y2)^2 giữa hai tọa độ bất kỳ.
Ví dụ: coordinates = {{1,2},{1,4},{3,5}}, đầu ra = 4.
Để giải quyết, ta dùng thuật toán quét đường (sweep line) kết hợp map:
- Định nghĩa map ytorightmostx.
- Sắp xếp mảng coordinates.
- ret := vô cùng.
- for mỗi p trong coordinates:
- it = lower_bound trong ytorightmostx với key p[1] - sqrt(ret).
- while it != end:
- yd = it->first - p[1]; nếu yd>0 và yd*yd >= ret: break.
- nxt = it; ++nxt.
- ret = min(ret, dist(p[0],p[1], it->second, it->first)).
- xd = it->second - p[0]; nếu xd*xd >= ret: xóa it khỏi map.
- it = nxt.
- ytorightmostx[p[1]] = p[0].
- Trả về ret.
- Hàm dist(xl,yl,xr,yr): xd=xl-xr; yd=yl-yr; trả xd*xd+yd*yd.
Ví dụ
Xem triển khai dưới đây:
#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