1549 - Dividindo a Coca

#include <bits/stdc++.h>

#define pb push_back
#define rep(i,a,b) for( int i = a; i < b; i++ )
#define debug(a) cout << #a << " = " << a << endl;
#define debug2(a,b) cout << #a << " = " << a << " --- " << #b << " = " << b << endl;
#define F first
#define S second

using namespace std;

typedef long long int ll;
typedef pair<int, int> ii;

// Forma mais segura e simples de se obter o valor de PI
// Arco cujo cosseno é -1, ou seja pi radianos
const double pi = acos(-1);

/*
*   Para resolvermos o problema de dividir a coca, podemos usar duas abordagens
*   - Solução matemática - funciona, mas talvez você gaste um bom tempo para chegar na forma final
*   - Matemática simples + busca binária - Geralmente é o ideal, pois existe menos chance de obtermos problemas de precisão
*     além de que provavelmente chegarimos a uma solução mais rapidamente - lembrem-se que na maratona cada minuto conta
*
*   Para usarmos a busca bibária vamos adotar o seguinte:
*   - o código "chuta" qual o valor da altura de coca que teremos em cada copo
*   - com a altura podemos calcular o volume presente no copo, e:
*       - se p/ ter esse volume em cada copo eu preciso de mais coca do que eu disponho, devemos diminuir a altura e com isso o volume
*       - caso contrário, podemos colocar um pouco mais de coca em cada copo aumentando a altura
*   - ao fim da busca, teremos o valor de h com a precisão estipulada pela busca
*
*   Dado um valor h, podemos usar a formula do volume do tronco de cone para calcular o valor
*                   Volume = pi/3 * (R*R+R*r+r*r) * h
*   Onde:
*   R: o raio da maior circulo do tronco
*   r: o raio do menor circulo o tronco
*   h: a altura do tronco
*   Note que, o valor de R varia de aacordo com o valor de h, ou seja, devemos estipular o valor de h com a busca binária
*   e cacular o valor de R para aquela atura, já o valor de r será o mesmo para qualquer altura
*
*   Para maior clareza, considere h como a altura total do copo e h' como a altura estipulada pela busca binária, respectivamente teremos
*   R como o raio do circulo na altura h e R' como raio do circulo na altura h'
*
*   h     C    B             |      Observe o desenho ao lado e o imagine como uma planificação da vista frontal do copo
*          \                |       Podemos notar que o triângulo ABC é semelhante ao triângulo ADE, logo, pode se perceber
*   h'      E  D           |        que a relação BC/AB = DE/AD é satisfeita, sabemos que AB = h e AD = h', sabemos também que
*            \            |         BC pode ser escrito como R - r, e DE como R'-r, logo isolando o valor de R', temos:
*             \          |                  R' = (R-r)*h'/h;
*              A________|
*
*
*/

int main(){

    int t, n;
    double r, R, h, V;

    cin >> t;
    while(t--){
        cin >> n >> V;
        cin >> r >> R >> h;

        // lo -> limite inferior da busca
        // hi -> limite superior da busca
        // hl -> altura que a busca binára "chutou" - h'
        double lo = 0, hi = h, hl;

        // Para buscas binárias com valores reais, o mais comum é estipular uma precisão,
        // nesse caso 1e-9 = 0.000000001, que é mais do que o suficiente para o problema
        // A busca só para quando esa precisão for atendida, ou seja, quando a diferença entre o maior e
        // o menor valor forem menores que 1e-9
        while(hi-lo > 1e-9){
            hl = (hi+lo)/2;
            double Rl = (R-r)*hl/h + r;  // Calcula R'
            double volume = pi/3 * h * (Rl*Rl + Rl*r + r*r);
            // verifica se aquele volume é o suficiente para N pessoas
            // Se sim, aumenta a altura, se não, diminui a mesma
            if(volume*n > V) hi = hl;
            else lo = hl;
        }
        cout << fixed << setprecision(2) << hl << endl;
    }
}
/*
2
1 200
5 6 8
2 350
3 3 16
*/