[BOJ] 2389 : 세상의 중심에서...

Drakk·2021년 8월 12일

C boj minimum enclosing cost 기하학 알고리즘 최소외접원 휴리스틱

알고리즘 문제풀이

목록 보기

22/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 x, y 좌표가 주어진다. 각각의 좌표는 소수점 여섯째자리까지 주어지며, -600,000 ≤ x, y ≤ 600,000을 만족한다.

🧺출력
첫째 줄에 김동혁의 x좌표, y좌표, 원의 반지름을 출력한다. 절대/상대 오차는 10-3까지 허용한다.

🔋예제 입출력

🔮예제 입력1
3
1 1
2 2
3 3

🔮예제 출력1
2 2 1.4142135624

💉문제 분석

🔋분류

휴리스틱, 최소외접원, 기하학

🔋난이도

다이아몬드V

💉문제 풀이

🔋해법

이 문제는 최소외접원 입문문제입니다.
저는 이론 + 기본코드 충분히 공부한다음에 문제풀이 시작했습니다.
여기서 공부했습니다.

보시면 코드가 살짝쿵 비슷한걸 느끼실수있으실겁니다.
살짝 다른부분은 저가 개인적으로 마스터할때까지, 코드실습을 무한반복하는 과정에서 살짝 코드가 달라진 부분도있습니다.

굿굿!

최소외접원의 원을 구해준다음에, 반지름의 소수점은 10번째짜리까지 표기해주면 됩니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr double INF = std::numeric_limits<double>::max();

struct Point{
	long double x, y;
	
	friend Point operator - (Point const& p1, Point const& p2){
		return { p1.x - p2.x, p1.y - p2.y };
	}
};

struct Circle{
	Point p;
	long double r;
};

double getDist(Point const A, Point const B){
	return (double)(std::sqrt(std::pow(A.x - B.x, 2) + std::pow(A.y - B.y, 2)));
}

Point calcCenter(Point const& A, Point const& B){
	long double XX = A.x * A.x + A.y * A.y;
	long double YY = B.x * B.x + B.y * B.y;
	long double D = A.x * B.y - A.y * B.x;
	
	return { (B.y * XX - A.y * YY) / (D * 2), (A.x * YY - B.x * XX) / (D * 2) };
}

Circle circleFrom(Point const& A, Point const& B){
	Point point = { (A.x + B.x) / 2.0, (A.y + B.y) / 2.0 };
	return { point, getDist(A, B) / 2.0 };
}

Circle circleFrom(Point const& A, Point const& B, Point const& C){
	Point point = calcCenter(B - A, C - A);
	point.x += A.x;
	point.y += A.y;
	
	return { point, getDist(point, A) };
}

bool isValid(std::vector<Point> const& p, Circle const& A){
	for(Point const& i : p){
		if(A.r < getDist(A.p, i)) return false;
	}
	
	return true;
}

Circle minimumEnclosingCost(std::vector<Point> const& p){
	int n = (int)p.size();
	
	if(n == 0) return { { 0, 0 }, 0.0 };
	if(n == 1) return { { p[0] }, 0.0 };
	
	Circle result = { { 0, 0 }, INF };
	
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			Circle temp = circleFrom(p[i], p[j]);
			
			if(temp.r < result.r && isValid(p, temp)) result = temp;
		}
	}
	
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			for(int k=j+1;k<n;++k){
				Circle temp = circleFrom(p[i], p[j], p[k]);
				
				if(temp.r < result.r && isValid(p, temp)) result = temp;
			}
		}
	}
	
	return result;
}

int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	
	std::vector<Point> pointList;
	int N;
	
	std::cin >> N;
	for(int i=0;i<N;++i){
		long double x, y;
		std::cin >> x >> y;
		
		pointList.push_back({ x, y });
	}
	
	Circle circle = minimumEnclosingCost(pointList);
	
	std::cout.precision(11);
	std::cout << circle.p.x << ' ' << circle.p.y << ' ' << circle.r;
}