BOJ 2022 - 사다리

[이전 블로그에서 글 옮김]

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

https://uva.onlinejudge.org/...&problem=1507

$a, b, c$ 가 주어지면 $k$ 를 구해내는 문제이다.

피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 $c$ 가 되는 순간을 구하도록 이분 탐색을 했다.

우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다.

$\begin{cases} A = \sqrt{a^2 - k^2} \\ B = \sqrt{b^2 - k^2} \end{cases}$

$\begin{cases} f(x) = \frac{B}{k}x \\ g(x) = -\frac{A}{k}x+A \end{cases}$

두 직선이 만나는 순간을 $(c_0, c)$라 한다면 $f(c_0) = g(c_0) = c$ 이여야 한다.

$\begin{align} f(c_0) = & \frac{B}{k}c_0 = c \\ & c_0 = \frac{k \cdot c}{B} \end{align}$

$g(c_0) = g(\frac{k \cdot c}{B}) = c$ 가 나온다면 정답일것이다.

$k$를 찾는 과정에서 $f(c_0) \gt c$ 라면 높이가 더 높은 좌표이므로 $c_0$을 줄여야한다는 뜻이다. $k$를 줄이면 $c_0$도 줄어든다.

$k$를 조정해서 만들어진 적당한 $x$로 $f(x) = g(x)$가 성립하는 지 확인하면서, 결과에 따라 $k$를 다시 조정하면 정답이 나온다.

$k$를 찾는 구간을 줄일 때 epsilon을 1e-5로 설정했을 때는 오답이었다. 이분탐색이 중간에 잘못되고 있나 생각에 구글링하다가 더 작은 결과까지 해보도록 1e-9 로 바꿨더니 정답을 맞았다. 너무 허무함

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 987654321
	double a, b, c;
	double g(double x, double k){
	double A = sqrt(a*a - k*k);
	return A - (A * x / k);
	}
	double f(double x, double k){
	return sqrt(b*b - k*k) * x / k;
	}
	int main(){
	while(~scanf("%lf %lf %lf", &a, &b, &c)){
	double l=0, r=min(a, b);
	while(r - l > 1e-9){
	double k = (l+r)/2.0;
	double c0 = k * c / sqrt(b*b - k*k);
	if(g(c0, k) > c){
	l = k;
	} else {
	r = k;
	}
	}
	printf("%.3lf\n", l);
	}
	return 0;
	}

view raw boj-2022.cpp hosted with ❤ by GitHub