題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3756
/**//*
題意：
在一個(gè)三維空間中，給定一些點(diǎn)，這些點(diǎn)的z坐標(biāo)都是大于0的。要求求
出一個(gè)圓錐（底面是圓形），使得這個(gè)圓錐的底面在z = 0的平面上，它能夠
包含所有給定的點(diǎn)并且圓錐的體積要求最小。
題解：
數(shù)學(xué)推導(dǎo) + 三分
思路：
這是一個(gè)很有意思的題，雖然是三維的，但是可以很容易的轉(zhuǎn)化到二維去
。來看X-Z這個(gè)平面，我們將所有的點(diǎn)進(jìn)行圓周映射，然后將所有的點(diǎn)都投影到
X-Z平面的的第一象限去，然后問題就轉(zhuǎn)化成了在X-Z平面上找到一條斜率為負(fù)
的直線L，L和X正方向、Z正方向圍成的三角形包含所有點(diǎn)，如果假設(shè)L和X軸的
交點(diǎn)為R，和Z軸焦點(diǎn)為H，要求pi*H*R^2的值最小。
然后我們來看看H和R之間有什么千絲萬縷的關(guān)系。首先L這條線必定和某一
個(gè)給定的點(diǎn)擦邊，也就是經(jīng)過那個(gè)點(diǎn)，我們假設(shè)它經(jīng)過P(a, b)， 并且L的斜率
為K(K < 0)，那么L的方程就可以表示為 L: y = K * (x - a) + b，則H和R就
可以利用這個(gè)方程表示出來：
H = -a * K + b;
R = -b / K + a;
那么所求的圓錐的體積就是：
V = pi*H*R^2 = pi * (-a * K + b) * (-b / K + a) ^ 2
容易得到V(K)這個(gè)函數(shù)的導(dǎo)數(shù)：
V'(K) = - pi * (aK^2 + 2bK) * (aK - b)^2 / K^2
影響這個(gè)導(dǎo)數(shù)的正負(fù)性的唯一條件是 -(aK^2 + 2bK)
當(dāng)-2b/a < K < 0時(shí)V'(K)大于零，也就是V的值是隨著K遞增的。
當(dāng)K < -2b/a時(shí)V'(K)小于零，也就是V的值是隨著K遞減的。
于是可以得出一個(gè)結(jié)論，當(dāng)K = -2b/a 時(shí)V取得最小值。
于是我們知道了V的單峰性，然后就可以通過枚舉半徑R，因?yàn)镽對于V具有單谷
性，所以枚舉R的時(shí)候可以采用三分。每次通過三分R找到最小的H，這個(gè)過程可
以通過枚舉每個(gè)點(diǎn)，找到最大的極角alpha，R*tan(alpha)就是H了。
這里需要注意的就是精度問題了。
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-6
const double pi = acos(-1.0);
struct Point 
{
double x, y, z;
double v, h;
void SCANF() {
scanf("%lf %lf %lf", &x, &y, &z);
v = z;
h = sqrt(x*x + y*y);
}
}pt[ 10001 ];
int n;
double MaxH, MaxV;
double Calc(double R) {
int i;
double Max = 0;
int idx = 0;
for(i = 0; i < n; i++) {
double nv = pt[i].v / (R - pt[i].h);
if(nv > Max) {
Max = nv;
idx = i;
}
}
return Max * R;
}
int main() {
int t;
int i;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
MaxH = MaxV = 0;
for(i = 0; i < n; i++) {
pt[i].SCANF();
if(pt[i].h > MaxH)
MaxH = pt[i].h;
if(pt[i].v > MaxV)
MaxV = pt[i].v;
}
double l = MaxH + eps, r = 1e6;
double ml, mr;
while(l + 1e-6 < r) {
ml = (2 * l + r) / 3;
mr = (l + 2 * r) / 3;
double lans = Calc(ml) * ml * ml;
double rans = Calc(mr) * mr * mr;
if( lans > rans ) {
l = ml + 1e-5;
}else
r = mr - 1e-5;
}
double ans = (l + r) / 2;
printf("%.3lf %.3lf\n", Calc(ans), ans);
}
return 0;
}