Dome of Circus

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 931 Accepted Submission(s): 417
Special Judge

Problem Description

A travelling circus faces a tough challenge in designing the dome for its performances. The circus has a number of shows that happen above the stage in the air under the dome. Various rigs, supports, and anchors must be installed over the stage, but under the dome. The dome itself must rise above the center of the stage and has a conical shape. The space under the dome must be air-conditioned, so the goal is to design the dome that contains minimal volume.
You are given a set of n points in the space; (xi, yi, zi) for 1 ≤ i ≤ n are the coordinates of the points in the air above the stage that must be covered by the dome. The ground is denoted by the plane z = 0, with positive z coordinates going up. The center of the stage is on the ground at the point (0, 0, 0).
The tip of the dome must be located at some point with coordinates (0, 0, h) with h > 0. The dome must have a conical shape that touches the ground at the circle with the center in the point (0, 0, 0) and with the radius of r. The dome must contain or touch all the n given points. The dome must have the minimal volume, given the above constraints.

Input

The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains a single integer number n (1 ≤ n ≤ 10 000) - the number of points under the dome. The following n lines describe points with three floating point numbers xi, yi, and zi per line - the coordinates of i-th point. All coordinates do not exceed 1000 by their absolute value and have at most 2 digits after decimal point. All zi are positive. There is at least one point with non-zero xi or yi.

Output

For each case , write to the output file a single line with two floating point numbers h and r - the height and the base radius of the dome. The numbers must be precise up to 3 digits after decimal point.

Sample Input

3
1
1.00 0.00 1.00
2
1.00 0.00 1.00
0.00 1.50 0.50
3
1.00 0.00 1.00
0.00 1.50 0.50
-0.50 -0.50 1.00

Sample Output

000 1.500
000 2.000
000 2.000

　　这题需要用到三分法，首先说一下题意，就是给你一堆点的坐标，它们都在XOY平面或上方，求一个体积最小的锥，使这些点都在锥的表面上，输出锥的高度和半径。

　　做法是这样的，首先我们要求的是一个锥的高度和半径，因此我们要将所有的点映射到第一卦限上面，然后转化为平面上的点，既转化为XOZ平面上的第一象限上的点，其中转化以后点的横坐标就是这点在锥上的半径。然后我们假设圆锥的底部半径就是r，那么可以根据数据的范围可以大概推算出r的范围，这一个范围就是三分的范围。然后可以分析得出无论是高度太大或者高度太小，圆锥的体积都会变大。我们的目标明显就是体积变化曲线的那个凹位。

　　这就是为什么要使用三分的原因，三分可以在一段连续变化的曲线中找某个极值点，条件是这段曲线在极值的两端都是单调的。具体做法见代码，其中代码并不是最好的做法，可以继续优化三分的范围可以缩小位左边界是半径最大的那个点这样速度可以提高很多。

上代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#define max(x,y) (x > y ? x : y)
#define MAX 10000+10
const double eps=1e-7;
using namespace std;

typedef struct
{
   double x,y,z;
   double r;
}point;

point p[MAX];

int n;

double ansv(double r)
{
   int i;
   double h,tmp;
   h=0;
   for(i=0;i<n;i++)
   {
       tmp=p[i].z*r/(r-p[i].r);
       h=max(tmp,h);
   }
   return h;
}

void trisearch()
{
   double L,R,mid,midl,midr,h;
   L=0;
   R=1000000.0;
   while(R-L>=eps)
   {
       mid=(L+R)/2;
       midl=(L+mid)/2;
       midr=(mid+R)/2;
       double hl=ansv(mid);
       double hr=ansv(midr);
       if(hl*mid*mid<hr*midr*midr) R=midr;
       else L=midl;
   }
   h=ansv(R);
   printf("%.3lf %.3lf
",h,R);
}

int main()
{
   int i,t;
   //freopen("data.txt","r",stdin);
   scanf("%d",&t);
   while(t--)
   {
       scanf("%d",&n);
       for(i=0;i<n;i++)
       {
           scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].z);
           p[i].r=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
       }
       trisearch();
   }
   return 0;
}
3756