二分+圆切面面积计算 boj1735

圆柱容器Submit: 31   Accepted:13Time Limit: 2000MS  Memory Limit: 65536KDescription

如图，这是一个奇怪的容器。它由n（n<=10）个首尾相连的圆柱体组成。这些圆柱体都紧靠在地面上，并且呈一条直线。每个圆柱体都有自己的长度L 和半径R 。我们可以向容器中注入自来水，假设这个容器的体积（即容量）是V。当容器注入V/2的水量时，求此时水面高于地面的高度H 。Baidu Camp的编程精英们，请帮steven解决这道难题吧。

Input
多组测试。每组数据的第一个数字为正整数n(1<=n<=10)，表示一共有n个圆柱体。接下来的n行，每行都有两个整数表示该圆柱体的半径和长度：R和L（R>0,L>0）


Output
对于每组数据，输出高于地面的水面高度H，保留三位小数


Sample Input

3
10 1
10 2
10 3
2
4 7
6 2


Sample Output

10.000
4.598

没有什么复杂的思路，关键是求圆切面的面积以及精度的控制。

#include <iostream>
#include <math.h>
using namespace std;

#define MIN 0.001
#define PI acos(-1)

typedef struct node
{
    int R, L;
}ST_CYC;

ST_CYC cyclind[15];


/*这里求圆切面的面积*/

double cal_v(int rr, double h, int L)
{
    double t, c, s, alpha;
    double R = (double)rr;

    s = PI * R * R;
    alpha = 2.0 * acos(fabs(h - R) / R);
    if (h < 2.0 * R && h > R)
    {
        s -= s * (alpha / (2.0 * PI));
        s += 0.5 * R * R * sin(alpha);
    }
    else if (h / 2.0 < rr)
    {
        s *= (alpha / (2.0 * PI));
        s -= 0.5 * R * R * sin(alpha);
    }
    return s * (double)L;
}


/*二分查找满足条件的值*/

double bin_find(int size, int max_R, double target)
{
    int i;
    double low, high, mid, V;

    high = 2 * max_R;
    low = 0;
    while (1)
    {
        mid = (low + high) / 2.0;
        V = 0;
        for (i=0 ; i<size ; i++)
            V += cal_v(cyclind[i].R, mid, cyclind[i].L);
        if (fabs(V - target) < MIN)
            break;
        if (V < target)
            low = mid;
        else
            high = mid;
    }
    return mid;
}

double all_v(int size)
{
    int i;
    double v = 0;
    for (i=0 ; i<size ; i++)
        v += cal_v(cyclind[i].R, cyclind[i].R * 2, cyclind[i].L);
    return v;
}

int main(int argc, char *argv[])
{
    int n, i, max_R;
    double V, ret;
    while (EOF != scanf("%d ", &n))
    {
        max_R = 0;
        for (i=0 ; i<n ; i++)
        {
            cin >> cyclind[i].R >> cyclind[i].L;
            if (cyclind[i].R > max_R)
                max_R = cyclind[i].R;
        }
        V = all_v(n);
        ret = bin_find(n, max_R, V / 2.0);
        printf("%.3lf\n", ret);
    }
}