本文主要是介绍HDU 3756 Dome of Circus 三分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在一个三维坐标中，有n个点（x，y，z），现在要用一个圆锥曲面（z>0）去覆盖住所有的点，点在圆锥曲面上也认为是覆盖。问当z=0时，圆锥曲面的半径和当（x，y=0）时，圆锥曲面的高为多少时？圆锥曲面的体积最小。
想法：首先先看二维图，设一个线段（x,0）<->（x,y），如果此时在x外围处有一个点为k，那么很显然当k越接近x时，则k与（x,y）构成的之间与y轴的交点越是大。所以当我们知道r的时候，我们可以枚举所有点与r上的点求斜率，取最大的那一个，显然当取最大时，此时的曲面可以把所有的其他点覆盖在内，那么现在的问题就是找出r，这里用三分去查找，注意他的上下界的选取。
#include<iostream>
#include<cmath>
#define pi acos(-1.0)
#define eps 1e-9
using namespace std;
int n;
struct node
{double x,y,z;
}dian[10000+5];
double cal(double r)
{double bl=-1;int id;for(int i=1;i<=n;i++){double k=dian[i].z/(r-sqrt(dian[i].x*dian[i].x+dian[i].y*dian[i].y));if(k>bl) {id=i;bl=k;}}double h=r*dian[id].z/(r-sqrt(dian[id].x*dian[id].x+dian[id].y*dian[id].y));return pi*r*r*h/3;
}
double cal1(double r)
{double bl=-1;int id;for(int i=1;i<=n;i++){double k=dian[i].z/(r-sqrt(dian[i].x*dian[i].x+dian[i].y*dian[i].y));if(k>bl) {id=i;bl=k;}}double h=r*dian[id].z/(r-sqrt(dian[id].x*dian[id].x+dian[id].y*dian[id].y));return h;
}
int main()
{int test;scanf("%d",&test);while(test--){scanf("%d",&n);double lft=-100000;for(int i=1;i<=n;i++){scanf("%lf%lf%lf",&dian[i].x,&dian[i].y,&dian[i].z);if(sqrt(dian[i].x*dian[i].x+dian[i].y*dian[i].y)>lft)lft=sqrt(dian[i].x*dian[i].x+dian[i].y*dian[i].y);}double rht=2000;while(rht-lft>eps){double mid=(lft+rht)/2;double midd=(mid+rht)/2;if(cal(mid)<cal(midd)){rht=midd;}else lft=mid;}printf("%.3lf %.3lf\n",cal1(lft),lft);}return 0;
}这篇关于HDU 3756 Dome of Circus 三分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
