C++에서 두 점 사이의 최단 거리를 찾는 프로그램

<시간/>

각 요소가 유클리드 좌표를 나타내는 [x, y] 형식인 좌표 목록이 있다고 가정합니다. 가장 작은 제곱 거리(x₁ - x₂ ) ² + (y₁ - y₂ ) ² 제공된 두 좌표 사이.

따라서 입력이 좌표 ={{1, 2},{1, 4},{3, 5}}와 같으면 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 지도 정의 ytorightmostx
배열 좌표 정렬
ret :=무한대
좌표의 각 p에 대해 -
- it =(p[1] - sqrt(ret))가 ytorightmostx에 있거나 ytorightmostx보다 큰 가장 작은 값을 반환
- ytorightmostx의 마지막 요소와 같지 않은 동안 −
  - yd :=첫 번째 - 그것의 p[1]
  - yd> 0이고 yd * yd>=ret이면 -
    - 루프에서 나오세요
  - nxt =그것
  - nxt를 1 증가
  - ret :=(ret, dist(p[0], p[1], 첫 번째 값, 두 번째 값)의 최소값
  - xd :=그것의 두 번째 값 - p[0]
  - xd * xd>=ret이면 -
    - ytorightmostx에서 삭제
  - 그것은 :=nxt
- ytorightmostx[p[1]] :=p[0]
리턴 렛
함수 dist()를 정의하십시오. xl, yl, xr, yr이 필요합니다.
- xd :=xl - xr
- yd :=일 - 년
- 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}}