C++で2点間の最短距離を見つけるプログラム

各要素が[x、y]の形式であり、ユークリッド座標を表す座標のリストがあるとします。最小の二乗距離（x ₁ ）を見つける必要があります -x ₂ ） ² +（y ₁ -y ₂ ） ² 提供された任意の2つの座標間。

したがって、入力が座標={{1、2}、{1、4}、{3、5}}のような場合、出力は4になります。

これを解決するには、次の手順に従います-

• 1つのマップを定義しますytorightmostx

• 配列座標を並べ替える

• ret：=無限大

• 座標の各pについて-

  • it =（p [1] --sqrt（ret））がytorightmostxにある値、またはytorightmostxからのそれよりも大きい最小値を返します

  • ytorightmostxの最後の要素と等しくありませんが、-

    を実行します。

    • yd：=最初-そのp[1]

    • yd>0かつyd*yd> =retの場合、-

      • ループから出てきます

    • nxt =it

    • nxtを1増やします

    • ret：=最小値（ret、dist（p [0]、p [1]、最初の値、2番目の値）

    • xd：=その2番目の値-p [0]

    • xd * xd> =retの場合、-

      • ytorightmostxから削除します

    • 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