The 47th World Championship ICPC I問題：Waterworld

問題. Waterworld

下図のように表面が分割された球が与えられる。水平方向には高さが等しくなるように $n$ 分割されており、垂直方向には $m$ 等分されている。 $j$ ステップ目のときの領域 $A_i$ の表面積に占める水の量の割合をパーセント表記したものを $a_{i, j}$ とする。
球全体の表面積に占める水の量の割合をパーセント表記で答えよ。

制約： $2 \le n, m \le 1,000$ 、 $0 \le a_{i, j} \le 100$

解法.

球の分割された各領域の表面積が等しいならば答えは $\frac{S}{n m}$ となり、実際そうなる。ただし、 $S = \sum_{1 \le i \le n, 1 \le j \le m} a_{i, j}$ とおく。

球の分割された各領域の表面積が等しいことを確認する。事実として、

球冠、球帯の表面積はその高さに比例する

ことが知られている（高校数学の美しい物語：球欠、球台の体積と球冠、球帯の表面積）。詳しい導出方法はリンク先を参照。
球帯とは球を二つの平行な平面で切った立体の側面部分である。したがって、上図の各 $1 \le i, i' \le n$ に対して、 $A_{i}, A_{i'}$ がそれぞれ含まれる球帯の高さが等しいので、上の事実から各球帯の表面積は等しい。また、各領域はそれが含まれる球帯を $m$ 等分しているので分割された各領域の表面積はすべて等しい。

計算時間： $O(1)$

検証：＠KATTIS

ソースコードを表示

#include <iostream>
#include <iomanip>

int main() {
    int n, m;
    std::cin >> n >> m;

    double sum = 0.0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            double a_ij;
            std::cin >> a_ij;
            sum += a_ij;
        }
    }

    std::cout << std::fixed << std::setprecision(9);
    std::cout << sum / (n * m) << std::endl;

    return 0;
}

極付近の分割された領域が球面三角形となっているので、初めは表面積が異なるのかなと思った。表面積の導出に手間取って大変だった。