Program to Find the Shortest Distance Between Two Points in C++

Suppose we have a list of coordinates where each element is of the form [x, y], representing Euclidean coordinates. We have to find the smallest squared distance (x₁ - x₂) ² + (y₁ - y₂) ² between any two provided coordinates.

So, if the input is like coordinates = {{1, 2},{1, 4},{3, 5}}, then the output will be 4.

To solve this, we will follow these steps −

• Define one map ytorightmostx

• sort the array coordinates

• ret := infinity

• for each p in cordinates −

  • it = return the value where (p[1] - sqrt(ret)) is in ytorightmostx or the smallest value greater than it from ytorightmostx

  • while it is not equal to last element of ytorightmostx, do −

    • yd := first - p[1] of it

    • if yd > 0 and yd * yd >= ret, then −

      • Come out from the loop

    • nxt = it

    • increase nxt by 1

    • ret := minimum of (ret, dist(p[0], p[1], first value of it, second value of it)

    • xd := second value of it - p[0]

    • if xd * xd >= ret, then −

      • delete it from ytorightmostx

    • it := nxt

  • ytorightmostx[p[1]] := p[0]

• return ret

• Define a function dist(), this will take xl, yl, xr, yr.

  • xd := xl - xr

  • yd := yl - yr

  • return xd * xd + yd * yd

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#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; }

Input

{{1, 2},{1, 4},{3, 5}}

Output

4