HDU：5432—Pyramid Split（二分）

二分

题面链接

• 问题描述

  小明是城会玩，他有很多底面是正方形的黄金锥体，我们称之为金字塔，它由高度和底面正方形边长可以确定，分别称之为金字塔的高和宽。
  为了便于理解，单位统一取米。现在小明有nn个金字塔，已知它们的高和宽，小明打算重铸，想将它重铸成两个体积一样的物体。
  当然，小明是城会玩，不会简单的把所有金字塔融了再分，他有一把屠龙刀，该刀削金如泥。
  他现在把所有金字塔正放(即底面贴地放)在水平地面上，用屠龙刀切割一个平面，该平面与水平面平行，称之为割平面。
  我们的任务是找到一个这样的割平面，使得这个割平面上方的体积之和等于下方的体积之和，该割平面称之为平均割平面。求平均割平面的高度。

• 输入描述

  第一行输入一个整数T，表示T组数据(1≤T≤100)。
  每组数据有三行，第一行有一个整数n，表示金字塔的个数(1≤n≤10000)。
  第二行有n个整数Ai，分别表示第i个金字塔的高度(1≤Ai≤1000)。
  第三行有n个整数Bi,分别表示第i个金字塔的宽度(1≤Bi≤100)。

• 输出描述

  对于每组数据，输出平均割平面的高度，取整数部分(如15.8请输出15)。

• 注意事项

  输入的时候要注意是先输入一串a，再输入一串b
  精度不能太低如0.1就会wrong

• 代码

#include<stdio.h>
#include<map>
#include<algorithm>
#include<string.h>
using namespace std;
double a[10010],b[10010];
double v1,v2,maxh;
int main()
{
    int t,n,i;
    scanf("%d",&t);
    while(t--)
    {
        maxh=-1;
        v1=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%lf",&a[i]);
            maxh=max(maxh,a[i]);
        }
        for(i=0;i<n;i++)
             scanf("%lf",&b[i]);
        for(i=0;i<n;i++)
            v1+=a[i]*b[i]*b[i];
        v1/=6;
        double l=0,r=maxh,v2,wide,mid;
        while(r-l>0.0001)
        {
            mid=(l+r)/2;
            v2=0;
            for(i=0;i<n;i++)
            {
                if(a[i]<=mid)
                    continue;
                wide=(a[i]-mid)/a[i]*b[i];
                v2+=wide*wide*(a[i]-mid)/3;
            }
            if(v2>v1)
                l=mid;
            else
                r=mid;
        }
        printf("%d\n",(int)l);
    }
    return 0;
}