用C ++查找两点之间最短距离的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个坐标列表，其中每个元素的格式为[x，y]，表示欧几里得坐标。我们必须找到任意两个提供的坐标之间的最小平方距离（x ₁ -x ₂）² +（y ₁ -y ₂）²。

因此，如果输入就像坐标= {{1，2}，{1，4}，{3，5}}，那么输出将为4。

在线示例

让我们看下面的实现以更好地理解-

#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

以上是 用C ++查找两点之间最短距离的程序 的全部内容， 来源链接： utcz.com/z/326364.html