首页 > ACM题库 > HDU-杭电 > HDU 3756-Dome of Circus-数据结构-[解题报告]HOJ
2015
04-10

HDU 3756-Dome of Circus-数据结构-[解题报告]HOJ

Dome of Circus

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

3.000 1.500
2.000 2.000
2.000 2.000

/*
分析:
    三分水题。
    是我想多了,cal的暴力部分不会TLE,囧~

                                              2012-12-21
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
#define N 10011
int n;
struct A
{
	double x,y,z;
	double r;
}E[N];
double cal(double R)
{
	int i;
	double temp,h=0;
	for(i=0;i<n;i++)					//没想到暴力能过,那么,有某有什么方法可以不用暴力的呢?
	{
		temp=E[i].z*R/(R-E[i].r);
		if(temp>h)	h=temp;
	}
	return h;
}
int main()
{
	int T;
	int i;
	double low,up,midl,midr,maxr,ansl,ansr;
	double temp1,temp2;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		maxr=0;
		for(i=0;i<n;i++)
		{
			scanf("%lf%lf%lf",&E[i].x,&E[i].y,&E[i].z);
			E[i].r=sqrt(E[i].x*E[i].x+E[i].y*E[i].y);
			if(E[i].r>maxr)	maxr=E[i].r;
		}
		low=maxr;up=3*maxr;
		while(up-low>1e-5)
		{
			midl=(up+2*low)/3;
			midr=(low+2*up)/3;
			temp1=cal(midl);
			temp2=cal(midr);
			ansl=temp1*midl*midl;
			ansr=temp2*midr*midr;
			if(ansl>ansr)	low=midl;
			else			up=midr;
		}
		printf("%.3lf %.3lf\n",temp1,up);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/8364324


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。