网站导航类型,加工平台有哪些设备,店铺店面装修,嘉兴seo收费POJ-2069 Super Star
题意#xff1a;
给你n个点#xff0c;求覆盖所有点的最小球的半径 4n30
题解#xff1a;
求最小球覆盖的步骤#xff1a; #xff08;1#xff09;对于一个点#xff1a;球心就是这个点#xff0c;且半径无穷小。 #xff08;2…POJ-2069 Super Star
题意
给你n个点求覆盖所有点的最小球的半径 4n30
题解
求最小球覆盖的步骤 1对于一个点球心就是这个点且半径无穷小。 2对于两个点球心就是两点线段的中点半径就是线段长度的一半。 3对于三个点三点构成的平面必为球的大圆球心是三角形的外心半径就是球心到某个点的距离。 4对于四个点若四点共面则转换到3点共面若四点不共面四面体可以唯一确定一个外接球。 5对于五个及以上的点最小球必为某四个点的外接球。 由此不难推导出最小球覆盖的球心一定与他距离最远的点有且最多有4个等距离的点。那么我们可以先假设一个点为球心找到与他距离最远的点并移动球心靠近该点不断重复此过程就能找到最小球覆盖的球心了。
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
struct point3{double x,y,z;
}point[40];
double dis(point3 a,point3 b){return sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y)(a.z-b.z)*(a.z-b.z));
}
int n;
const double eps1e-6;
double solve(){double step100,ans1e10,mt;point3 c;c.xc.yc.z0;int s0;while(stepeps){for(int i1;in;i)if(dis(c,point[s])dis(c,point[i]))si;//距离c最远的点sdouble Disdis(c,point[s]);// c与s的距离,相当于半径 c.x(point[s].x-c.x)/Dis*step;c.y(point[s].y-c.y)/Dis*step;c.z(point[s].z-c.z)/Dis*step;ansmin(ans,Dis);step*0.98;}return ans;
}
int main()
{rd_test();double ans;while(cinnn){for(int i1;in;i){cinpoint[i].xpoint[i].ypoint[i].z;}anssolve();printf(%.5f\n,ans);}return 0;//Time_test();
}
