HDU 3756 Dome of Circus
英雄哪里出来发表于 2011-04-12 14:58:00
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3756
/**//*
题意： 在一个三维空间中，给定一些点，这些点的z坐标都是大于0的。要求求出一个圆锥（底面是圆形），使得这个圆锥的底面在z = 0的平面上，它能够包含所有给定的点并且圆锥的体积要求最小。题解： 数学推导 + 三分思路： 这是一个很有意思的题，虽然是三维的，但是可以很容易的转化到二维去。来看X-Z这个平面，我们将所有的点进行圆周映射，然后将所有的点都投影到X-Z平面的的第一象限去，然后问题就转化成了在X-Z平面上找到一条斜率为负的直线L，L和X正方向、Z正方向围成的三角形包含所有点，如果假设L和X轴的交点为R，和Z轴焦点为H，要求pi*H*R^2的值最小。 然后我们来看看H和R之间有什么千丝万缕的关系。首先L这条线必定和某一个给定的点擦边，也就是经过那个点，我们假设它经过P(a, b)， 并且L的斜率为K(K < 0)，那么L的方程就可以表示为 L: y = K * (x - a) + b，则H和R就可以利用这个方程表示出来：H = -a * K + b;R = -b / K + a;那么所求的圆锥的体积就是：V = pi*H*R^2 = pi * (-a * K + b) * (-b / K + a) ^ 2容易得到V(K)这个函数的导数：V'(K) = - pi * (aK^2 + 2bK) * (aK - b)^2 / K^2影响这个导数的正负性的唯一条件是 -(aK^2 + 2bK)当-2b/a < K < 0时V'(K)大于零，也就是V的值是随着K递增的。当K < -2b/a时V'(K)小于零，也就是V的值是随着K递减的。于是可以得出一个结论，当K = -2b/a 时V取得最小值。于是我们知道了V的单峰性，然后就可以通过枚举半径R，因为R对于V具有单谷性，所以枚举R的时候可以采用三分。每次通过三分R找到最小的H，这个过程可以通过枚举每个点，找到最大的极角alpha，R*tan(alpha)就是H了。 这里需要注意的就是精度问题了。
*/
#include <iostream>#include <cmath>#include <algorithm>using namespace std;#define eps 1e-6const 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;}