首页 > 代码库 > POJ2069 最小球体覆盖, 模拟退火
POJ2069 最小球体覆盖, 模拟退火
只是套了个模板,模拟退火具体的过程真心不懂阿
1 //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler 2 #include <stdio.h> 3 #include <iostream> 4 #include <cstring> 5 #include <cmath> 6 #include <stack> 7 #include <queue> 8 #include <vector> 9 #include <algorithm>10 #define ll long long11 #define Max(a,b) (((a) > (b)) ? (a) : (b))12 #define Min(a,b) (((a) < (b)) ? (a) : (b))13 #define Abs(x) (((x) > 0) ? (x) : (-(x)))14 using namespace std;15 16 const int INF = 0x3f3f3f3f;17 const int MAXN = 220;18 const double eps = 1e-8;19 int n;20 struct POINT{21 double x,y,z;22 }ps[35],q;23 24 double dist(POINT a,POINT b){25 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));26 }27 28 int maxD(POINT p){29 double res = 0;30 int i, k = 0;31 for(i = 0; i < n ; ++i){32 double tmp = dist(p,ps[i]);33 if(tmp > res){34 k = i;35 res = dist(p,ps[i]);36 }37 }38 return k;39 }40 41 double BallCover(){42 double step = 100, ans = INF;43 q.x = q.y = q.z = 0.0;44 while(step > eps){45 int d = maxD(q);46 double tmp = dist(ps[d],q);47 if(tmp < ans) ans=tmp;48 double dx = ps[d].x - q.x;49 double dy = ps[d].y - q.y;50 double dz = ps[d].z - q.z;51 dx /= tmp;52 dy /= tmp;53 dz /= tmp;54 q.x += (dx*step);55 q.y += (dy*step);56 q.z += (dz*step);57 step *= 0.98;58 }59 return ans;60 }61 62 int main(){63 int i;64 while(EOF != scanf("%d",&n)){65 if(0 == n) break;66 for(i = 0; i < n ; ++i)67 scanf("%lf%lf%lf",&ps[i].x,&ps[i].y,&ps[i].z);68 printf("%.5f\n",BallCover());69 }70 return 0;71 }
POJ2069 最小球体覆盖, 模拟退火
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。