随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 3756 Dome of Circus

题目链接: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-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*+ 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;
}

posted on 2011-04-12 22:58 英雄哪里出来 阅读(967) 评论(0)  编辑 收藏 引用 所属分类: 数学


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理