백준 14583번 이음줄 (c++)

문제만 보고 어떻게 접으라는건지 파악하기가 힘들어서 오래걸렸다

 

https://mygumi.tistory.com/166

해당 블로그에서 잘 도식화 해놓아서 참고했다.

 

아무튼 접힌 점 E와 F는 특정하게 몇등분된 지점이 아니므로 이분탐색해서 구해버려야 할것이다.

 

먼저 d의 길이는 피타고라스의 정리로 구할 수 있다.

double d = sqrt(h * h + v * v);

 

삼각형 ABC와 ABE는 직각삼각형의 닮음 성질을 이용할 수 있는 형태이므로

 

h:d = a:b 라는 비례식을 구할 수 있다.

해당 비례식과 a+b는 v라는 사실을 이용해 이분탐색을 진행하면

 

double low = 0;
double high = v;
while (high - low > 0.001f)
{
	double mid = (low + high) / 2.0f;
	double a = mid;
	double b = v - mid;
	if (b * h > a * d) {
		low = mid;
	}
	else {
		high = mid;
	}
}

a,b값을 구할 수 있다.

 

목표한 직사각형의 가로값은 절반 접은것이므로 c/2 일 것이다.

a를 알고 있으므로 c값을 구할 수 있다.

double vertical = sqrt(low * low + h * h) / 2.0f;

 

평행사변형 BECF의 밑변의 길이는 아니까 넓이를 알면 높이 k를 구할 수 있을것이다.

직사각형 내의 평행사변형은 움직여도 넓이가 동일하므로 b * h 직사각형과 같은 넓이일것이다

double hight = ((v - low) * h) / (vertical * 2);

cout << round(vertical * 100) / 100.0f << " " << round(hight*100)/100.0f << endl;

소수점 3번째 자리에서 반올림 하라 했으므로 round를 통해 반올림 해준다.