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 :=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