โปรแกรมหาระยะทางที่สั้นที่สุดระหว่างจุดสองจุดใน C++

สมมติว่าเรามีรายการพิกัดที่แต่ละองค์ประกอบอยู่ในรูปแบบ [x, y] ซึ่งเป็นตัวแทนของพิกัดแบบยุคลิด เราต้องหาระยะกำลังสองที่เล็กที่สุด (x₁ - x₂ ) ² + (y₁ - y₂ ) ² ระหว่างสองพิกัดที่ให้ไว้

ดังนั้น หากอินพุตเป็นเหมือนพิกัด ={{1, 2},{1, 4},{3, 5}} ผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่ ytorightmostx

• จัดเรียงพิกัดอาร์เรย์

• ret :=อินฟินิตี้

• สำหรับแต่ละ p ในพิกัด -

  • มัน =ส่งคืนค่าโดยที่ (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 :=yl - ปี

  • คืนค่า 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