c6150fed.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const f64 H = 100.0;
const f64 S = H * H;
const f64 EPS = 1e-8;
const f64 PI = 3.14159265358979323846;

const int N = 10000 + 5;

struct Sphere
{
    f64 r;
    f64 x, y, z;
    f64 volume;

    inline void initialize(const int &r, const int &x, const int &y, const int &z)
    {
        this->r = r / 1000.0;
        this->x = x / 1000.0;
        this->y = y / 1000.0;
        this->z = z / 1000.0;
        this->volume = 4.0 / 3.0 * PI * this->r * this->r * this->r;
    }
    inline f64 cap(const double &h) const
    {
        return PI * h * h * (r - h / 3.0);
    }
    inline f64 min() const
    {
        return z - r;
    }
    inline f64 max() const
    {
        return z + r;
    }
};

int n, s;
Sphere sphere[N];

inline f64 calc(f64 cut)
{
    f64 res = cut * S;
    for (int i = 1; i <= n; ++i)
    {
        if (sphere[i].max() < cut)
        {
            res -= sphere[i].volume;
        }
        else if (sphere[i].min() < cut)
        {
            res -= sphere[i].cap(cut - sphere[i].min());
        }
    }
    // watch(res);
    return res;
}

inline int sign(const f64 &x)
{
    if (fabs(x) < EPS)
    {
        return 0;
    }
    return x > 0.0 ? 1 : -1;
}

int main()
{
    read(n), read(s);

    f64 V = H * H * H;
    for (int i = 1, r, x, y, z; i <= n; ++i)
    {
        read(r), read(x), read(y), read(z);
        sphere[i].initialize(r, x, y, z);
        V -= sphere[i].volume;
    }

    const f64 per = V / (f64)s;
    f64 cur = 0.0;
    for (int i = 1, sgn; i <= s; ++i)
    {
        f64 L = cur, R = 100.0, mid;
        while (L + EPS < R)
        {
            mid = (L + R) / 2.0;
            sgn = sign(calc(mid) - per * i);
            if (sgn == 0)
            {
                break;
            }
            if (sgn == 1)
            {
                R = mid;
            }
            else
            {
                L = mid;
            }
        }
        printf("%.8f\n", mid - cur);
        cur = mid;
    }

    return 0;
}