Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में दो बिंदुओं के बीच सबसे छोटी दूरी ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास निर्देशांकों (coordinates) की एक सूची है जहां प्रत्येक एलिमेंट [x, y] के रूप में है, जो यूक्लिडियन निर्देशांक दर्शाता है। हमें किन्हीं दो दिए गए निर्देशांकों के बीच सबसे छोटी वर्ग दूरी (squared distance) (x₁ - x₂)² + (y₁ - y₂)² ढूंढनी है।

तो, यदि इनपुट coordinates = {{1, 2}, {1, 4}, {3, 5}} है, तो आउटपुट 4 होगा।

समाधान दृष्टिकोण

स्वीप लाइन एल्गोरिदम (Sweep Line Algorithm) का उपयोग करते हुए। निर्देशांकों को x के अनुसार सॉर्ट करें। एक मैप y → राइटमोस्ट x बनाए रखें। प्रत्येक बिंदु के लिए, केवल उन बिंदुओं की जांच करें जिनका y-निर्देशांक √ret के भीतर है।

उदाहरण कोड

#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

व्याख्या

बिंदु (1,2) और (1,4): दूरी² = (1-1)² + (2-4)² = 0 + 4 = 4

बिंदु (1,4) और (3,5): दूरी² = (1-3)² + (4-5)² = 4 + 1 = 5

बिंदु (1,2) और (3,5): दूरी² = (1-3)² + (2-5)² = 4 + 9 = 13

न्यूनतम = 4

निष्कर्ष

स्वीप लाइन + बैलेंस्ड BST (map) दृष्टिकोण O(n log n) समय में काम करता है, जो ब्रूट फोर्स O(n²) से बेहतर है। यह क्लोजेस्ट पेयर ऑफ पॉइंट्स समस्या का एक वेरिएंट है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें एक 2D ऐरे दिया गया है जो त्रिभुज के तीन शीर्षों के निर्देशांक को दर्शाता है। हमारा कार्य C++ में त्रिभुज के केंद्रक (Centroid) ज्ञात करने का प्रोग्राम बनाना है।केंद्रक (Centroid) त्रिभुज का वह बिंदु है जहां त्रिभुज की तीनों मध्यिकाएं (medians) प्रतिच्छेद करती हैं।मध्यिका (Median)

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ

  1. बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें दो नोड्स u और v के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है - अब (4, 6) के बीच की दूरी = 4, पथ की लंबाई 4 है, (5, 8) के बीच की लंबाई = 5 आदि। इस समस्या को हल करने के लिए, हम LCA (निम्नतम सामान्य पूर्वज) खोजेंगे, फिर LCA से दो नोड