BOJ 11930 | Smallest Enclosing Sphere

$f(x, y)$에 대해 최소 외접원을 구하는 방법은 세상의 중심에서(#2389) 포스팅에서 자세히 설명했다.

동일한 방법으로 $f(x, y, z)$에 대한 최소 외접구를 구할 수 있다. 그러니까 그냥 똑같은 문제라고 생각하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Point{
	double x, y, z;
};

int main(){
	FASTIO;
	int N; cin >> N;
	vector<Point> fan;
	for (int i = 0; i < N; i++){
		double a, b, c; cin >> a >> b >> c;
		fan.push_back({a, b, c});
	}
	
	double w = 0.1;
	Point center = {0, 0, 0};
	
	for (auto &i: fan){
		center.x += i.x/N;
		center.y += i.y/N;
		center.z += i.z/N;
	}
	
	double mxdist, radius = 0;
	Point mnPoint;
	for (int i = 0; i < 200000; i++){
		// get Radius
		mxdist = 0; Point mxPoint;
		for (auto &i: fan){
			double dist = sqrt((center.x - i.x)*(center.x - i.x)+(center.y - i.y)*(center.y - i.y)+(center.z - i.z)*(center.z - i.z));
			if (mxdist < dist){
				mxPoint = i; mxdist = dist;
			}
		}
		
		// set center
		center.x = center.x + (mxPoint.x - center.x)*w;
		center.y = center.y + (mxPoint.y - center.y)*w;
		center.z = center.z + (mxPoint.z - center.z)*w;
		w *= 0.9999;
	}
	printf("%.2f", round(mxdist*100)/100);
	//printf("%.3f %.3f\n%.3f", round(center.x*1000)/1000, round(center.y*1000)/1000, round(mxdist*1000)/1000);
}