【POJ】2069.Super Star

题解

求一个最小的半径的球，包括三维平面上所有的点，输出半径

随机移动球心，半径即为距离最远的点，移动的方式是向离的最远的那个点移动一点，之后模拟退火就好

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

//#define ivorysi

#define MAXN 105

#define eps 1e-8

#define pb push_back

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

struct Point {

    db x,y,z;

    Point(db _x = 0,db _y = 0,db _z = 0) {

	x = _x;y = _y;z = _z;

    }

}P[35];

int N;

u32 Rand() {

    static u32 x = 1736382156;

    return x += x << 2 | 1;

}

db Rand_p() {

    return (db) (Rand() % 10000) / 10000;

}

inline db o(db x) {return x * x;}

db dist(Point a,Point b) {

    return sqrt(o(a.x - b.x) + o(a.y - b.y) + o(a.z - b.z));

}

db get_radius(Point a) {

    db res = dist(a,P[1]);

    for(int i = 2 ; i <= N ; ++i) res = max(res,dist(P[i],a));

    return res;

}

int get_farthest(Point a) {

    int r = 1;

    for(int i = 2 ; i <= N ; ++i) {

	if(dist(a,P[i]) > dist(a,P[r])) r = i;

    }

    return r;

}

void Solve() {

    db delta = 0.99,T = 1000;

    db now = get_radius(P[1]),ans = now;

    Point s = P[1];

    while(T > eps) {

	ans = min(ans,now);

	int c = get_farthest(s);

	db d = dist(P[c],s);

	Point t = Point(s.x + (P[c].x - s.x) / d * T,s.y + (P[c].y - s.y) / d * T,s.z + (P[c].z - s.z) / d * T);

	db r = get_radius(t);

	if(r <= now) {

	    now = r,s = t;

	}

	else {

	    if(exp((now - r) / T) > Rand_p()) {

		now = r,s = t;

	    }

	}

	T *= delta;

    }

    printf("%.5f\n",ans);

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    while(scanf("%d",&N) != EOF && N) {

	for(int i = 1 ; i <= N ; ++i) {

	    scanf("%lf%lf%lf",&P[i].x,&P[i].y,&P[i].z);

	}

	Solve();

    }

}

巴特西

【POJ】2069.Super Star

题解

代码

最新文章

热门文章