AtCoder题解｜Pyramid

AtCoder题解｜ABC 112C Pyramid

---

题目信息 📚

【题目描述】

In the Ancient Kingdom of Snuke, there was a pyramid to strengthen the authority of Takahashi, the president of AtCoder Inc.

The pyramid had center coordinates $(C_X, C_Y)$ and height $H$. The altitude of coordinates $(X, Y)$ is $\max(H - |X - C_X| - |Y - C_Y|, 0)$.

Aoki, an explorer, conducted a survey to identify the center coordinates and height of this pyramid. As a result, he obtained the following information:

• $C_X, C_Y$ were integers between $0$ and $100$ (inclusive), and $H$ was an integer not less than $1$.
• Additionally, he obtained $N$ pieces of information. The $i$-th of them is: “the altitude of point $(x_i, y_i)$ is $h_i$.”

This was enough to identify the center coordinates and the height of the pyramid. Find these values with the clues above.

【输入】

The input is given from Standard Input in the following format:

$N$

$x_1$ $y_1$ $h_1$

$x_2$ $y_2$ $h_2$

$\vdots$

$x_N$ $y_N$ $h_N$

【输出】

Print values $C_X, C_Y$ and $H$ representing the center coordinates and the height of the pyramid in one line, with spaces in between.

【数据范围】

• $N$ is an integer between $1$ and $100$ (inclusive).
• $x_i$ and $y_i$ are integers between $0$ and $100$ (inclusive).
• $h_i$ is an integer between $0$ and $10^9$ (inclusive).
• The $N$ coordinates $(x_1, y_1), (x_2, y_2), (x_3, y_3), …, (x_N, y_N)$ are all different.
• The center coordinates and the height of the pyramid can be uniquely identified.

【输入样例1】

4
2 3 5
2 1 5
1 2 5
3 2 5

【输出样例1】

2 2 6

In this case, the center coordinates and the height can be identified as $(2,2)$ and $6$.

【输入样例2】

2
0 0 100
1 1 98

【输出样例2】

0 0 100

• In this case, the center coordinates and the height can be identified as $(0,0)$ and $100$. Note that $C_X$ and $C_Y$ are known to be integers between $0$ and $100$.

【输入样例3】

3
99 1 191
100 1 192
99 0 192

【输出样例3】

100 0 193

• In this case, the center coordinates and the height can be identified as $(100,0)$ and $193$.

【题目来源】

https://atcoder.jp/contests/abc112/tasks/abc112_c

---

题目解析 🍉

【题目分析】

数学思维 + 枚举

$(x_{ans}, y_{ans})$ 的范围仅有 $100*100 = 1e4$ ，因此可以枚举所有可能的坐标。

对于每一个枚举的坐标，需要将其与 $N$ 条信息（最大 $100$ 条）进行验证。

经过推理，一条信息可以带来的贡献如下：

• 若 $h[i] > 0$，则 $h[i] = \max(H - |X - C_X| - |Y - C_Y|, 0) > 0$，说明 $max$ 函数取了前半部分。
  • 则 $h[i] = H - |X - C_X| - |Y - C_Y|$ → $H = h[i] + |X - C_X| + |Y - C_Y|$
  • 即该条信息提供了一个且仅有一个 $H$ 值（定值）
• 若 $h[i] = 0$，则 $h[i] = \max(H - |X - C_X| - |Y - C_Y|, 0) = 0$，说明 $max$ 函数中的 $H - |X - C_X| - |Y - C_Y| \leq 0$。
  • 即 $H - |X - C_X| - |Y - C_Y| \leq 0$ → $H \leq |X - C_X| - |Y - C_Y|$
  • 即该条信息提供了 $H$ 的一个上限值（其他 $N - 1$ 条得到的 $H$ 均要满足这个条件）

因此，$N$ 条信息可以在 $O(N)$ 的时间内进行验证，故总时间复杂度为 $O(XYN)$ 为 $1e6$ 量级，可以实现。

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 110;
LL x[N], y[N], h[N], n;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入n条信息
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> h[i];

    // 枚举所有可能点 (0, 0) -> (100, 100)
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            // 验证点(i, j)
            set<LL> s;
            LL hmax = INT_MAX;
            for (int k = 1; k <= n; k++) {  // 根据n条信息，得到所有可能的h值与上限hmax
                if (h[k] > 0) {  // 得到所有可能的h值
                    LL H = h[k] + abs(i - x[k]) + abs(j - y[k]);
                    s.insert(H);
                } else if (h[k] == 0) {  // 得到上限hmax
                    hmax = min(abs(i - x[k]) + abs(j - y[k]), hmax);
                }
            }
            // 验证h的可能值是否只有一个且h <= hmax
            if (s.size() == 1 && hmax >= *s.begin()) {
                // 若符合，直接输出答案
                cout << i << " " << j << " " << *s.begin() << endl;
                return 0;
            }
        }
    }
    return 0;
}