HDU 5432 Pyramid Split

时间：2024-11-15 23:05:37

题意：有n个底面是正方形的四棱锥，用一个水平截面将所有四棱锥分成两半，要求上一半体积的和等于下一半，求水平截面的高度，输出整数部分。

解法：二分截面高度。比赛的时候二分写不明白了orz……

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

double const eps = 1e-3;

double a[10005], b[10005];

int n;

int cal(double mid)

{

    double sum1 = 0.0, sum2 = 0.0;

    for(int i = 0; i < n; i++)

    {

        if(mid > a[i])

        {

            sum2 += a[i] * b[i] * b[i] / 3.0;

            continue;

        }

        double vsum = a[i] * b[i] * b[i] / 3.0;

        double x = (a[i] - mid) * b[i] / a[i];

        double lvsum = (a[i] - mid) * x * x / 3.0;

        sum1 += lvsum;

        sum2 += vsum - lvsum;

    }

    if(fabs(sum1 - sum2) < eps) return 0;

    if(sum1 > sum2) return 1;

    return -1;

}

int solve()

{

    double l = 0.0, r = 1000.0;

    double mid;

    while((r-l)>= eps)

    {

        mid = (l + r) / 2.0;

        int tmp = cal(mid);

        if(tmp == 0) return mid;

        else if(tmp == 1) l = mid + eps;

        else r = mid - eps;

    }

    return mid;

}

int main()

{

    int T;

    while(~scanf("%d", &T))

    {

        while(T--)

        {

            scanf("%d", &n);

            for(int i = 0; i < n; i++)

                scanf("%lf", &a[i]);

            for(int i = 0; i < n; i++)

                scanf("%lf", &b[i]);

            printf("%d\n", (int)solve());

        }

    }

    return 0;

}

　　

while(r - l > 1)

{

    LL mid = (l + r) >> 1;

    if(judge(mid)) l = mid;

    else

       r = mid;

}

cout << l << endl;

/*贴一个实验室大神的二分模板*/

　　

相关文章