Processing math: 100%

C++程序找出建筑物的中心坐标和高度


假设,有一栋建筑物,其中心坐标为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)

示例

让我们看看以下实现以获得更好的理解:

Open Compiler
#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; }

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输入

3, {3, 3, 2}, {4, 2, 3}, {6, 6, 6}

输出

3 3 7

更新于: 2022年3月2日

235 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告