परिचय
मान लीजिए हमारे पास निर्देशांकों (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²) से बेहतर है। यह क्लोजेस्ट पेयर ऑफ पॉइंट्स समस्या का एक वेरिएंट है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।