โปรแกรม C++ หาพิกัดศูนย์กลางและความสูงของอาคาร

มีอาคารที่มีพิกัดศูนย์กลาง (xc, yc) และความสูง h (ไม่ทราบค่า) ได้รับข้อมูล n จุด แต่ละจุดมีพิกัด (x, y) และค่าความสูง a ที่คำนวณจากสูตร max(h - |x - xc| - |y - yc|, 0) ต้องการหา xc, yc, h จากข้อมูลเหล่านี้

ตัวอย่าง: n = 3, x = {3, 3, 2}, y = {4, 2, 3}, a = {6, 6, 6} ผลลัพธ์: 3 3 7 (ศูนย์กลางที่ 3,3 ความสูง 7)

ขั้นตอนการแก้ปัญหา (Brute Force)

1. วนลูป xc = 0 ถึง 100 และ yc = 0 ถึง 100
2. สำหรับแต่ละคู่ (xc, yc) ตรวจสอบความสอดคล้อง:
   • คำนวณ k = |x[i]-xc| + |y[i]-yc| สำหรับทุก i
   • ถ้า a[i] == 0 เก็บ mh = min(mh, k)
   • ถ้า a[i] > 0 ต้องมี h = a[i] + k คงที่สำหรับทุก i ที่ a[i] > 0
   • ตรวจสอบ h <= mh (ถ้าไม่ผ่าน ข้ามคู่นี้)
3. พิมพ์ xc, yc, h ของคู่แรกที่ผ่านเกณฑ์

ตัวอย่างโค้ด 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 < n; i++) {
                int 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;
}

อินพุต / เอาต์พุต

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

Output: 3 3 7