题目地址：UVa：UVa Online Judge、洛谷：【UVA1712】Cutting Cheese – 洛谷

题目描述

原题面参见UVa/vjudge。
给你一个100*100*100的大方块，里面有若干球形空缺，要求切成s个体积相同的小方块，求每一块的厚度。

题解

简单的计算几何。
我们考虑球形体积和球缺体积的算法
\begin{aligned} V_{\text{ball}} &= \frac{4}{3} \pi r^3 \\ V_{\text{cap}} &= \pi h^2 (r - \frac{h}{3}) \end{aligned}
对于每一块，我们二分计算它与之前所有块加起来的厚度（因为这样只需要考虑切面的球缺），每次计算块体积的时候遍历球体，如果完全包含减体积，如果部分包含减球缺体积，

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>

typedef long double LD;

const int MAXN = 10005;
const LD PI = acos(-1), EPS = 1e-12;

inline LD getballv(LD r) {
    return r * r * r * 4 / 3 * PI;
}

inline LD getballvq(LD r, LD h) {
    return PI * (3 * r - h) * h * h / 3;
}

int n, s;
LD z[MAXN], r[MAXN], len[MAXN], v;

inline LD getblockv(LD l) {
    LD res = l * 100 * 100;
    for(int i = 1; i <= n; i++) {
        if(z[i] + r[i] <= l) {
            res -= getballv(r[i]);
        } else if(z[i] - r[i] < l) {
            res -= getballvq(r[i], r[i] - z[i] + l);
        }
    }
    return res;
}

inline LD cal(LD v) {
    LD l = 0, r = 100, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(getblockv(mid) <= v) l = mid; else r = mid;
    }
    return l;
}

int main() {
    while(scanf("%d%d", &n, &s) != EOF) {
        v = 100 * 100 * 100;
        for(int i = 1; i <= n; i++) {
            scanf("%Lf%*d%*d%Lf", &r[i], &z[i]);
            r[i] *= 0.001; z[i] *= 0.001;
            v -= getballv(r[i]);
        }
        for(int i = 1; i <= s; i++) {
            len[i] = cal(i * v / s);
        }
        for(int i = 1; i <= s; i++) {
            printf("%.10Lf\n", len[i] - len[i - 1]);
        }
    }
    return 0;
}