[Day 4] BOJ 13202 : 피자 배치

khj20006·2022년 11월 3일

기하학

100 Day Algorithm Challenge

목록 보기

5/6

문제

https://www.acmicpc.net/problem/13202

직각삼각형에서 내접원들을 넓이가 큰 순서대로 계속해서 N개를 그려나갔을 때,
그 중 K번째 원의 넓이를 구하는 문제입니다.

해결 전략

제일 큰 원을 기준으로 각 꼭짓점 방향으로 내접원을 계속 그려나갔을 때,
넓이의 순서를 알 수 있는 방법을 몰라서 저는 그냥 각 방향의 원을 100개씩 다 구해서 내림차순 정렬을 해줬습니다.

위 그림에서 빨간 선 위의 원들에 대한 반지름의 비를 구하고,
파란 선 위의 원들에 대한 반지름의 비를 구하여 넓이들을 모두 배열 하나에 저장합니다.

닮음비 구하기 (빨간 선)

삼각형의 밑변을 $a$ , 높이를 $b$ , 원 $i$ 의 반지름을 $r_i$ 이라고 하겠습니다.

먼저, 원 $1, 2, 4, 7, ...$ 들의 닮음비를 구해봅시다.

위 그림에서,
선분 $\overline{AC}$ 의 길이는 피타고라스 정리에 의해 $\sqrt{(a-r_1)^2+{r_1}^2}$ 이고,
선분 $\overline{AD}$ 의 길이가 $r_1+r_2$ 이므로 선분 $\overline{DC}$ 의 길이는 $\overline{AC}-\overline{AD}$ 입니다.

삼각형 $ACB$ 와 삼각형 $DCE$ 를 살펴봅시다.
두 삼각형에서 $\angle ABC = \angle DEC$ 이고, $\angle ACB = \angle DCE$ 입니다.
이는 곧 두 삼각형이 닮음이라는 걸 의미합니다.

닮음비 식을 다음과 같이 세울 수 있고 우리는 $\overline{DE}$ , 즉 $r_2$ 의 값을 구하면 됩니다.

$\overline{AB} : \overline{AC} = \overline{DE} : \overline{DC}$

$\overline{AB} = r_1$

$\overline{AC} = \sqrt{(a-r_1)^2+{r_1}^2}$

$\overline{DC} = \overline{AC}-\overline{AD}$

저는 여기서 계산을 편하게 하기 위해, $bottom$ 과 $d$ 라는 변수를 두어 각각 다음을 저장했습니다.

$bottom$ = 원 $i$ 의 중심에서 내린 수선의 발과 꼭짓점 $C$ 까지의 거리
$d$ = (원 $i$ 의 중심에서 $C$ 까지의 거리) - $r_i$

코드 상에서는 대입 연산자가 있어 $i$ 번째라고 지정해주지 않아도 되지만, 설명하기 위해
$i$ 번째 원의 각 변수를 $bottom_i, d_i, r_i$ 라고 하겠습니다.

각 변수는 점화식 형태로 표현이 가능합니다.

$i=1$ 일 때,

$r_1 = \dfrac{a+b-\sqrt{a^2+b^2}}{2}$
$bottom_1 = a-r_1$
$d_1 = \sqrt{{bottom_1}^2+{r_1}^2} - r_1$

$i>1$ 일 때,

$r_i = \dfrac{{d}{r_{i-1}}}{d+2r_{i-1}}$
$bottom_i = \sqrt{{d_{i-1}}^2 - 2d_{i-1}r_i}$
$d_1 = \sqrt{{bottom_1}^2+{r_1}^2} - r_1$

닮음비 구하기 (파란 선)

이 경우는 아까의 경우보다 훨씬 간단합니다.

삼각형 $ABH$ 와 삼각형 $FGH$ 역시 같은 이유로 서로 닮음입니다.

닮음비를 세워보면, $\overline{FG} : \overline{HF} = \overline{AB} : \overline{HA}$ 이고, 이 식을 정리하면 아래와 같습니다.

$r_{i+1} = (3-2\sqrt{2})r_i\space\space\space\space\space\space(i\ge1)$

이제, 구현할 차례입니다.

코드

#define _USE_MATH_DEFINES
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

bool cmp(double a, double b) { return a > b; }

int main() {
	int T;
	cout.setf(ios::fixed);
	cout.precision(6);
	for (cin >> T; T--;) {
		double a, b, S[303]{};
		int k, id = 0;
		cin >> a >> b >> k;
		double r = ((a + b) + sqrt(a * a + b * b)) / 2;
		if (r >= min(a, b))	r = ((a + b) - sqrt(a * a + b * b)) / 2;
		S[id++] = r * r * M_PI;
		double r2 = r, r3 = r;
		double bot = a - r;
		double d = sqrt(bot * bot + r * r) - r;
		r = r * d / (2 * r + d);
		S[id++] = r * r * M_PI;
		for (int i = 0; i < k - 1; i++) {
			bot = sqrt(d * d - 2 * d * r);
			d = sqrt(bot * bot + r * r) - r;
			r = r * d / (2 * r + d);
			S[id++] = r * r * M_PI;
		}
		bot = b - r2;
		d = sqrt(bot * bot + r2 * r2) - r2;
		r2 = r2 * d / (2 * r2 + d);
		S[id++] = r2 * r2 * M_PI;
		for (int i = 0; i < k - 1; i++) {
			bot = sqrt(d * d - 2 * d * r2);
			d = sqrt(bot * bot + r2 * r2) - r2;
			r2 = r2 * d / (2 * r2 + d);
			S[id++] = r2 * r2 * M_PI;
		}
		r3 = (3 - 2 * sqrt(2)) * r3;
		S[id++] = r3 * r3 * M_PI;
		for (int i = 0; i < k - 1; i++) {
			r3 = (3 - 2 * sqrt(2)) * r3;
			S[id++] = r3 * r3 * M_PI;
		}
		sort(S, S + id, cmp);
		cout << S[k - 1] << '\n';
	}
	cout.unsetf(ios::fixed);
}