Chương trình tìm khoảng cách ngắn nhất giữa hai điểm trong C ++

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 ₁ - x ₂ ) ² + (y ₁ - y ₂ ) ² 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