মান লিজিয়ে, একটি ভবনের কেন্দ্রস্থান হলো (xc, yc) এবং উচ্চতা h। আমরা ভবনের কেন্দ্রস্থান জানি না, কিন্তু আমাদের n টি তথ্য দেওয়া আছে যাতে x এবং y কোঅর্ডিনেট এবং একটি উচ্চতার মান a রয়েছে। কোঅর্ডিনেট (x, y)-র উচ্চতা হলো max(h - |x - xc| - |y - yc|, 0)। আমাদের লক্ষ্য হলো ভবনের কেন্দ্রস্থান (xc, yc) এবং উচ্চতা h নির্ণয় করা। x কোঅর্ডিনেট 'x' অ্যারেতে, y কোঅর্ডিনেট 'y' অ্যারেতে এবং a মান 'a' অ্যারেতে দেওয়া আছে।
যেমন, ইনপুট হলে n = 3, x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6}, তবে আউটপুট হবে 3 3 7।
কেন্দ্রস্থান হলো (3,3) এবং ভবনের উচ্চতা হলো ৭।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
check := true xc := 0 থেকে ১০০ পর্যন্ত: yc := 0 থেকে ১০০ পর্যন্ত: check := true mh := 2000000000 h := -1 i := 0 থেকে n-1 পর্যন্ত: k := |x[i] - xc| + |y[i] - yc| if a[i] == 0, তবে: mh := min(mh, k) অন্যথায়: if h < 0, তবে: h := a[i] + k অন্যথায় যদি h != a[i] + k, তবে: check := false লুপ থেকে বের হয়ে যান if h > mh, তবে: check := false পরবর্তী ইটারেশনে যান if check সত্য, তবে: লুপ থেকে বের হয়ে যান if check সত্য, তবে: বাহ্যিক লুপ থেকে বের হয়ে যান 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
