[Day 3-1] BOJ 2022 : 사다리

다리가 4개면? 사다리 ㅋㅋㅋ....

문제

• https://www.acmicpc.net/problem/2022

두 빌딩이 얼마나 떨어져 있을까?

해결 전략

처음에는 단순히 피타고라스 정리만을 이용해 식을 도출해내려고 했지만, 식이 너무너무 복잡해져서 포기했습니다.
$O(1)$만에 답을 구하는 건 불가능이라 생각해서 근삿값을 찾아가며 푸는 문제라고 생각을 해봤습니다.

구하려는 값을 $h$로 두고 이를 근삿값으로 사용합니다. 초기에는 $0$과 $min(x,y)$의 중간으로 설정합니다.

왼쪽 집과 길이 $y$인 선분이 닿는 바닥 지점을 원점으로 하여 두 점선이 이루는 직선의 방정식을 각각 구하고,
그들의 교점의 $y$좌표와 $c$값을 비교합니다.

만약 $c$보다 크다면, $h$가 더 길어져야 $y$좌표가 점점 아래로 내려올 것이므로 구간 이등분 후 오른쪽 구간에 대하여 탐색을 계속합니다.
만약 $c$보다 작다면, 왼쪽 구간에 대하여 탐색합니다.
만약 $c$와의 오차가 문제에서 요구하는 만큼 충분히 작다면, 즉 거의 같다면, $h$가 답이 됩니다.

코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	double a, b, c;
	cin >> a >> b >> c;
	double s = 0, e = min(a, b), h = (s + e) / 2;
	double beta = sqrt(b * b - h * h) * sqrt(a * a - h * h) / (sqrt(b * b - h * h) + sqrt(a * a - h * h));
	while (abs(beta - c) > 0.00001) {
		if (beta > c)	s = h;
		else if (beta < c)	e = h;
		h = (s + e) / 2;
		beta = sqrt(b * b - h * h) * sqrt(a * a - h * h) / (sqrt(b * b - h * h) + sqrt(a * a - h * h));
	}
	cout.setf(ios::fixed);
	cout.precision(3);
	cout << h;
}

회고

처음에 삽질한 흔적... 문제를 풀 때 발상의 전환을 잘 해야 겠다고 느꼈습니다..