C++-এ دوটি বিন্দুর মধ্যে ন্যূনতম দূরত্ব বের করুন

মান লিজিয়ে коорডিনেটের একটি লিস্ট আছে যেখানে প্রতিটি এলিমেন্ট [x, y] ফর্মে, যৌক্লিডিয়ান коорডিনেট উপস্থাপন করে। আমাদের যেকোনো দুটি коорডিনেটের মধ্যে ন্যূনতম বর্গ দূরত্ব (x₁ - x₂)² + (y₁ - y₂)² বের করতে হবে।

যেমন ইনপুট coordinates = {{1, 2},{1, 4},{3, 5}} হলে আউটপুট হবে ৪।

সমাধানের ধাপগুলো:

একটি ম্যাপ ytorightmostx সংজ্ঞায়িত করুন
coordinates অ্যারে সর্ট করুন
ret := infinity
প্রতিটি p ইন coordinates-এ:

it = ytorightmostx.lower_bound(p[1] - sqrt(ret))
যখন it != ytorightmostx.end():

yd := it->first - p[1]
যদি yd > 0 এবং yd*yd >= ret, ব্রেক করুন
nxt = it; nxt++
ret := min(ret, dist(p[0], p[1], it->second, it->first))
xd := it->second - p[0]
যদি xd*xd >= ret, ytorightmostx.erase(it)
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}}