题目链接:题目链接
题目大意:三维空间有n个点,找到另外一个点,离所有点的最大距离最小。求这个距离。
这个点的任意坐标,在其他两个坐标确定的情况下,最大距离都是一个单峰函数,那么就可以三分套三分套三分。
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-3
int n;
struct node{
double p[3];
}a[100005];
double MAX_DIT(node ans){
double MAX=0;
for(int i=1; i<=n; i++){
MAX=max(MAX, sqrt((ans.p[0]-a[i].p[0])*(ans.p[0]-a[i].p[0])+(ans.p[1]-a[i].p[1])*(ans.p[1]-a[i].p[1])+(ans.p[2]-a[i].p[2])*(ans.p[2]-a[i].p[2])));
}
return MAX;
}
node sf(int cut, node now){
if(cut>=3){
return now;
}
node ans, Lans, Rans;
double L=-100000, R=100000, LL, RR;
ans=Lans=Rans=now;
//for(int i=1; i<=50; i++) 严格控制三分的次数 防T
while(eps<R-L){
LL=(2*L+R)/3, RR=(2*R+L)/3;//两个三分点
Lans.p[cut]=LL, Rans.p[cut]=RR;//赋值
Lans=sf(cut+1, Lans);//继续三分下个轴的坐标
Rans=sf(cut+1, Rans);//继续三分下个轴的坐标
if(MAX_DIT(Lans)>MAX_DIT(Rans)){
ans=Lans, L=LL;
}
else{
ans=Rans, R=RR;
}
}
return ans;
}
int main(){
while(~scanf("%d", &n)){
for(int i=1; i<=n; i++){
scanf("%lf%lf%lf", &a[i].p[0], &a[i].p[1], &a[i].p[2]);
}
node ans;
printf("%.8f\n", MAX_DIT(sf(0, ans)));
}
}