मान लीजिए कि हमारे पास निर्देशांक की एक सूची है जहां प्रत्येक तत्व [x, y] के रूप में है, जो यूक्लिडियन निर्देशांक का प्रतिनिधित्व करता है। हमें सबसे छोटी वर्ग दूरी ज्ञात करनी है (x1 - x<उप>2 ) 2 + (वाई<उप>1 - वाई<उप>2 ) 2 दिए गए किन्हीं दो निर्देशांकों के बीच।
इसलिए, यदि इनपुट निर्देशांक ={{1, 2},{1, 4},{3, 5}} जैसा है, तो आउटपुट 4 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक मानचित्र को ytorightmostx परिभाषित करें
-
सरणी निर्देशांक क्रमबद्ध करें
-
रिट:=अनंत
-
निर्देशांक में प्रत्येक p के लिए -
-
it =वह मान लौटाएं जहां (p[1] - sqrt(ret)) ytorightmostx में है या ytorightmostx से इससे सबसे छोटा मान है
-
जबकि यह ytorightmostx के अंतिम तत्व के बराबर नहीं है, −
. करें-
yd :=पहले - p[1] इसका
-
यदि yd> 0 और yd * yd>=ret, तो -
-
लूप से बाहर आएं
-
-
एनएक्सटी =यह
-
1 से आगे बढ़ाएँ
-
रिट:=न्यूनतम (रिट, डिस्ट (पी [0], पी [1], इसका पहला मूल्य, इसका दूसरा मूल्य)
-
xd :=इसका दूसरा मान - p[0]
-
अगर xd * xd>=ret, तो -
-
इसे ytorightmostx से हटाएं
-
-
यह:=अगला
-
-
ytorightmostx[p[1]] :=p[0]
-
-
वापसी रिट
-
एक फ़ंक्शन को परिभाषित करें dist(), इसमें xl, yl, xr, yr लगेगा।
-
एक्सडी:=एक्सएल - एक्सआर
-
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
