मान लीजिए, एक इमारत है जिसका केंद्र xc, yc, और ऊंचाई h है। हम भवन के केंद्र निर्देशांक को नहीं जानते हैं, लेकिन हमें n जानकारी प्रदान की जाती है जिसमें x और y निर्देशांक होते हैं और ऊंचाई मान a होता है। निर्देशांकों की ऊंचाई (x, y) अधिकतम (h - |x - xc| - |y - yc|, 0) है। हमें केंद्र के निर्देशांक और इमारत की ऊंचाई का पता लगाना है। निर्देशांक xi सरणी x में दिया गया है, yi तेग सरणी y में दिया गया है, और ai सरणी a में दिया गया है।
इसलिए, यदि इनपुट n =3, x ={3, 3, 2}, y ={4, 2, 3}, a ={6, 6, 6} जैसा है, तो आउटपुट 3 3 7 होगा।
केंद्र के निर्देशांक 3,3 हैं और भवन की ऊंचाई 7 है।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
check := true for initialize xc := 0, when xc <= 100, update (increase xc by 1), do: for initialize yc := 0, when yc <= 100, update (increase yc by 1), do: check := true mh := 2000000000 h := -1 for initialize i := 0, when i < n, update (increase i by 1), do: k := |(x[i] - xc) + |y[i] - yc|| if a[i] is same as 0, then: mh := minimum of mh and k else: if h < 0, then: h := a[i] + k otherwise when h is not equal to a[i] + k, then: check := false Come out from the loop if h > mh, then: check := false Ignore following part, skip to the next iteration if check is non-zero, then: Come out from the loop if check is non-zero, then: Come out from the loop print(xc, yc, h)
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
void solve(int n, vector<int> x, vector<int> y, vector<int> a){
bool check = true;
int xc, yc, h;
for (xc = 0; xc <= 100; xc++) {
for (yc = 0; yc <= 100; yc++) {
check = true;
int k, mh = 2e9;
h = -1;
for(int i = 0; i < n; i++) {
k = abs(x[i] - xc) + abs(y[i] - yc);
if (a[i] == 0) {
mh = min(mh, k);
} else {
if (h < 0) {
h = a[i] + k;
} else if (h != a[i] + k) {
check = false;
break;
}
}
}
if (h > mh) {
check = false;
continue;
}
if (check) {
break;
}
}
if (check) {
break;
}
}
cout << xc << " " << yc << " " << h;
}
int main() {
int n = 3;
vector<int> x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6};
solve(n, x, y, a);
return 0;
} इनपुट
3, {3, 3, 2}, {4, 2, 3}, {6, 6, 6} आउटपुट
3 3 7