CCPC-Wannafly Winter Camp Day2 (Div2, onsite)

H. Cosmic Cleaner

Description:

在一片小行星带里有 $n$ 颗小行星，它们在万有引力的作用下绕着一颗行星旋转。在这一刻时，它们之间不存在碰撞的情况。一位清洁工奉命前来清理这颗行星，Ta 会动用某种先进技术使这颗行星顷刻间从宇宙中消失，任何距离这颗行星的中心在一定范围内的事物都会在一瞬间被清除。假设这些天体都是完整的球体，你能计算出清除的区域里有多少体积的事物原本属于这些小行星吗？

注意，这些天体在此刻满足两两不存在交集的条件。

下图是对样例的解释，其中清理区域是标记为红色的球体内部，而小行星则被依次标记为橙色、蓝色和绿色。

Input:

输入包含多组测试数据。第一行包含一个整数 $T$ ，表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据：

第一行包含一个整数 $n$ 。

接下来的 $n$ 行里，每行包含四个整数 $x, y, z$ 和 $r$ ，表示有一颗中心位于 $(x, y, z)$ 、半径为 $r$ 的小行星。

最后一行包含四个整数 $x', y', z' 和 r'$ ，表示行星的中心位于 $(x', y', z')$ ，而清洁工的清理半径为 $r'$ （一个大于该行星半径的值）。

$1 \leq T \leq 6000$
$1 \leq n \leq 100$
$- 1 0^{3} \leq x, y, z, x', y', z' \leq 1 0^{3}$
$1 \leq r, r' \leq 1 0^{3}$

Output:

对于每组测试数据，输出一行Case #x: y，其中x是测试数据的编号（从 $1$ 开始编号），y是这组数据的答案，要求相对误差或绝对误差不超过 $1 0^{- 6}$ 。

严格来讲，如果你的答案是 $a$ ，而标准答案是 $b$ ，那么当 $\frac{∣ a - b ∣}{\max 1, ∣ b ∣} \leq 1 0^{- 6}$ 时你的答案会被认为是正确的。

Sample Input:

1
3
5 5 5 2
-6 -7 6 1
6 -5 0 3
1 -1 0 10

Sample Output:

Case #1: 142.76246874761383764962

题目链接

计算一球与其余 $n$ 个球的球交体积。

计算球交的重点在于球缺的计算，推荐一篇详解博客（现场赛我也是现学的这篇博客…雾）

两圆相交到两球相交

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e2 + 5;
const double pi = acos(-1.0);
const double eps = 1e-8;

int Sgn(double X) {
    if (fabs(X) < eps) {
        return 0;
    }
    return X < 0 ? -1 : 1;
}

struct Point {
    double X, Y, Z;

    void Input() {
        scanf("%lf%lf%lf", &X, &Y, &Z);
    }
};

typedef Point Vector;

Vector operator + (Vector Key1, Vector Key2) {
    return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y, Key1.Z + Key2.Z};
}

Vector operator - (Vector Key1, Vector Key2) {
    return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y, Key1.Z - Key2.Z};
}

double operator * (Vector Key1, Vector Key2) {
    return Key1.X * Key2.X + Key1.Y * Key2.Y + Key1.Z * Key2.Z;
}

double Length(Vector Key) {
    return sqrt(Key * Key);
}

double operator ^ (Vector Key1, Vector Key2) {
    return Length((Vector){Key1.Y * Key2.Z - Key1.Z * Key2.Y, Key1.Z * Key2.X - Key1.X * Key2.Z, Key1.X * Key2.Y - Key1.Y * Key2.X});
}

double DisPointToPoint(Point Key1, Point Key2) {
    return sqrt((Key1 - Key2) * (Key1 - Key2));
}

struct Sphere {
    Point Center;
    double Radius;

    void Input() {
        Center.Input();
        scanf("%lf", &Radius);
    }
};

double CalVolume(Sphere Key) {
    return 4.0 / 3.0 * pi * Key.Radius * Key.Radius * Key.Radius;
}

double SphereIntersectVolume(Sphere Key1, Sphere Key2) {
    double Ans = 0.0;
    double Dis = DisPointToPoint(Key1.Center, Key2.Center);
    if (Sgn(Dis - Key1.Radius - Key2.Radius) >= 0) {
        return Ans;
    }
    if (Sgn(Key2.Radius - (Dis + Key1.Radius)) >= 0) {
        return CalVolume(Key1);
    }
    else if (Sgn(Key1.Radius - (Dis + Key2.Radius)) >= 0) {
        return CalVolume(Key2);
    }
    double Length1 = ((Key1.Radius * Key1.Radius - Key2.Radius * Key2.Radius) / Dis + Dis) / 2;
    double Length2 = Dis - Length1;
    double X1 = Key1.Radius - Length1, X2 = Key2.Radius - Length2;
    double V1 = pi * X1 * X1 * (Key1.Radius - X1 / 3.0);
    double V2 = pi * X2 * X2 * (Key2.Radius - X2 / 3.0);
    return V1 + V2;
}

int T;
int N;
Sphere Planet[maxn];
Sphere Clean;
double Ans;

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i) {
            Planet[i].Input();
        }
        Clean.Input();
        Ans = 0.0;
        for (int i = 1; i <= N; ++i) {
            Ans += SphereIntersectVolume(Clean, Planet[i]);
        }
        printf("Case #%d: %.20lf\n", Case, Ans);
    }
    return 0;
}