Chương trình C++ tìm tâm và chiều cao tòa nhà từ dữ liệu độ cao

Mô tả bài toán

Có tòa nhà với tâm (xc, yc) và chiều cao h. Biết n điểm quan trắc: tại (x[i], y[i]) độ cao là a[i] = max(h - |x-xc| - |y-yc|, 0). Tìm xc, yc, h (0 ≤ xc,yc ≤ 100).

Ví dụ

n=3, x={3,3,2}, y={4,2,3}, a={6,6,6}. Đầu ra: 3 3 7 (tâm (3,3), cao 7).

Thuật toán

1. Duyệt mọi cặp (xc, yc) trong [0,100].
2. Với mỗi cặp, tính k = |x[i]-xc| + |y[i]-yc|.
3. Nếu a[i]==0 thì h ≤ k → cập nhật mh = min(mh, k).
4. Nếu 0 thì h = a[i] + k phải giống nhau cho mọi i có a[i]>0.
5. Kiểm tra h ≤ mh. Cặp đầu tiên thỏa mãn là kết quả.

Đoạn mã C++

#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 mh = 2e9;
            h = -1;
            for(int i=0;i 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;
}

Đầu vào / Đầu ra

Input: 3, {3,3,2}, {4,2,3}, {6,6,6}

Output: 3 3 7