HDU 5432 Pyramid Split

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

暴力

Description

Xiao Ming is a citizen who's good at playing,he has lot's of gold cones which have square undersides,let's call them pyramids.

Anyone of them can be defined by the square's length and the height,called them width and height.

To easily understand,all the units are mile.Now Ming has n pyramids,there height and width are known,Xiao Ming wants to make them again to get two objects with the same volume.

Of course he won't simply melt his pyramids and distribute to two parts.He has a sword named "Tu Long" which can cut anything easily.

Now he put all pyramids on the ground (the usdersides close the ground)and cut a plane which is parallel with the water level by his sword ,call this plane cutting plane.

Our mission is to find a cutting plane that makes the sum of volume above the plane same as the below,and this plane is average cutting plane.Figure out the height of average cutting plane.

Input

First line: T, the number of testcases.(1≤T≤100)

Then T testcases follow.In each testcase print three lines :

The first line contains one integers n(1≤n≤10000), the number of operations.

The second line contains n integers A1,…,An(1≤i≤n,1≤Ai≤1000) represent the height of the ith pyramid.



The third line contains n integers B1,…,Bn(1≤i≤n,1≤Bi≤100) represent the width of the ith pyramid.

Output

For each testcase print a integer - **the height of average cutting plane**.

(the results take the integer part,like 15.8 you should output 15)

Sample Input

2
2
6 5
10 7
8
702 983 144 268 732 166 247 569
20 37 51 61 39 5 79 99

Sample Output

1
98

题意：

有n个正四棱锥，把他们放在同一个水平面上，用一条线把它切割，要求上部分的体积总和=下半部分的体积总和；输出这个线放的高度；

解题思路：

要求上部分体积之和=下部分体积之和即上部分体积之和=总体积的二分之一；设四棱锥高=h[i]，底面边长=a[i]；设线方的高度为k，根据相似比有(（h[i]-k）^3/h[i]^3)*(h[i]*a[i]*a[i])的总和=(1/2)*(h[i]*a[i]*a[i])的总和;

完整代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
double h[10010];
double a[10010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        double maxn=0.0,s=0.0;
        for(int i=0;i<n;i++)
        {
             scanf("%lf",&h[i]);
             maxn=max(maxn,h[i]);
        }
        for(int i=0;i<n;i++)
        {
             scanf("%lf",&a[i]);
             s+=h[i]*a[i]*a[i];
        }
        s/=2.0;
        double j;
        int ans=0;
        for(j=1;j<maxn;j++)
        {
            double sum=0.0;
             for(int i=0;i<n;i++)
            {
                if(h[i]<=j)
                    continue;
                double x=(h[i]-j)*(h[i]-j)*(h[i]-j);
                double y=h[i]*h[i];
                double z=a[i]*a[i];
                sum+=z*x/y;
            }
            if(sum<s)
             {
                 ans=(int)j-1;
                 break;
             }
            else if(sum==s)
             {
                 ans=(int)j;
                 break;
             }
             //break;
        }
        printf("%d\n",ans);
    }
    return 0;
}