BOJ 21182 | Weird Flecks, But OK

문제를 처음 보면 조금 당황할 수 있는데 'The drill may enter any one of the cube faces, but must be positioned orthogonally to the face. ' 문장만 없다면 문제가 좀 어려워지기 때문이다.

그래서 난 3차원 공간에서 최소 외접 실린더를 구하는 미쳐버린 문제인 줄 알았는데 큐브에 수직으로 드릴을 삽입하니 모양이 3개로 고정되어버린다.

결국 최소 외접원을 3번 구하는 것이나 다름이 없기 때문에 문제가 아주 간단해진다. (이게 왜 다이아)

코드

#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'

int N; 

struct Point{
	double x, y;
};

double getDist(vector<Point> fan){
	double w = 0.1;
	Point center = {0, 0};
	
	for (auto &i: fan){
		center.x += i.x/N;
		center.y += i.y/N;
	}
	
	double mxdist, radius = 0;
	Point mnPoint;
	for (int i = 0; i < 10000; 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));
			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;
		w *= 0.99;
	}
	return mxdist;
}

int main(){
	FASTIO;
	cin >> N;
	vector<Point> fan1, fan2, fan3;
	for (int i = 0; i < N; i++){
		double a, b, c; cin >> a >> b >> c;
		fan1.push_back({a, b});
		fan2.push_back({b, c});
		fan3.push_back({a, c});
	}	
	
	printf("%.8f", min(getDist(fan1), min(getDist(fan2), getDist(fan3)))*2 );
	//printf("%.3f %.3f\n%.3f", round(center.x*1000)/1000, round(center.y*1000)/1000, round(mxdist*1000)/1000);
}