풀이
요약: 양 끝점이 고정된 길이 L의 선분이 있다. 이 선분의 가운데를 이쁘게 늘려서 길이 L+d의 곡선을 만든다. 그럼 길이 L의 현과 길이 L+d의 호가 만들어진다. 이 때, 현의 중심과 호의 중심까지의 거리 x는 얼마일까?
알고리즘에 수학을 싸서 드셔보세요!!
주어진 호를 예쁘게 연장해서 예쁜 원을 만들어주자.
원의 중심에서 현의 끝점까지 예쁜 반지름 r1, r2도 그어주자.
현을 이등분하는 예쁜 반지름 r3도 그어주자.
r3와 r2, r3와 r1 사이의 각을 세타라고 하자.
삼각함수를 이용해서 식을 잘 정리하면 반지름의 길이를 구할 수 있고,
세타도 구할 수 있고,
이어서 답도 구할 수 있다.
근데 지금 술이 안 깨서 못 쓸 거 같으니 유도는 직접 해보는 게 좋을 거 같다.
아무튼 정리하면 (sin세타)/세타 = L/(L+d)를 만족하는 세타를 찾아야 하는데,
저 식의 좌변이 아마 답 범위 내에서 감소함수인가? 기억이 잘 안 난다. (궁금하면 미분해보자)
암튼 그래서 이분탐색으로 세타를 찾을 수 있다.
코드
#include <cstdio>
#include <cmath>
int tc;
double L, LD, R, l, r, th;
int main() {
for (scanf("%d", &tc); tc--;) {
scanf("%lf %lf", &L, &LD);
LD += L, l = 0, r = 3.142;
for (int i = 0; i < 50; i++) {
th = (l+r)/2;
(sin(th)/th<L/LD ? r : l) = th;
}
r = LD/2/th;
printf("%.0lf\n", r*(1-cos(th)));
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이