मान लीजिए एक इमारत है जिसके केंद्र निर्देशांक xc, yc और ऊँचाई h हैं। हमें केंद्र निर्देशांक ज्ञात नहीं हैं, लेकिन हमारे पास n जानकारियाँ हैं जिनमें x, y निर्देशांक और ऊँचाई मान a है। निर्देशांक (x, y) की ऊँचाई max(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
xc := 0 से 100 तक:
yc := 0 से 100 तक:
check := true
mh := 2000000000
h := -1
i := 0 से n-1 तक:
k := |x[i] - xc| + |y[i] - yc|
यदि a[i] == 0, तो:
mh := min(mh, k)
अन्यथा:
यदि h < 0, तो:
h := a[i] + k
अन्यथा यदि h != a[i] + k, तो:
check := false
लूप से बाहर निकलें
यदि h > mh, तो:
check := false
अगली पुनरावृत्ति पर जाएँ
यदि check सत्य है, तो:
लूप से बाहर निकलें
यदि check सत्य है, तो:
लूप से बाहर निकलें
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
