[Algospot] 달과 그림자

문제 정보

문제ID

MOON

출제자

Taeyoon_Lee

출처

2014 KAIST ACM-ICPC 모의대회

시간제한

3000ms

메모리제한

65536kb

분류

.

문제 설명

달과 그림자의 반지름 m, s와 두 중심사이의 거리 c가 주어졌을 때 그림자에 가려지지 않은 달의 넓이를 구하는 공식 문제입니다.

m, s, c의 조건은 다음과 같이 주어집니다.

(2 <= m < s < c <= 12, c < m + s)

풀이 과정

우선 두원이 겹치는 경우의 수는 다음과 같이 4가지의 경우의 수로 나누어 볼 수 있습니다.

case 1 : 두 원이 완전히 겹치는 경우 (c <= s - m)
case 2 : 두 원이 겹치지 않는 경우 (c > s + m)
case 3 : 한개의 원의 중심이 다른 원에 포함 된 경우 (c < s)
case 4 : 원의 중심과 두원이 맞닿는 점을 잇는 선들의 각도가 모두 예각인 경우.

여기서 m, s, c의 조건을 확인한 결과 우리는 4번 case의 경우만 고려하면 된다는 것을 알 수 있습니다.

그럼 문제를 풀기위해 위 그림에 중심선과 두원이 맞닿는 점, 그리고 두 중심섬을 잇는 선을 그리고 주어진 정보 m, s, c를 표시하면 다음과 같습니다.

설명을 위해 편의상 각 점들을 대문자 M, S와 A, B로 표기하였습니다.

위 그림을 보신분들 중 문제를 해결하기 위한 방법을 눈치채신 분들도 있으실 것 같습니다.

문제에서 요구하는 답은 겹치지 않는 노란색 원의 넓이입니다. 이를 구하기 위해, 도형을 다음과 같이 분리할 수 있습니다.

두개의 원과 M,A,B를 잇는 부채꼴과 삼각형, S,A,B를 있는 부채꼴과 삼각형.

여기서 다음과 같은 식을 만들어 볼 수 있습니다.

원(M) - ( 부채꼴(M,A,B) - 삼각형(M,A,B) ) - ( 부채꼴(S,A,B) - 삼각형(S,A,B) )
= 원(M) + 삼각형(M,A,B) + 삼각형(S,A,B) - 부채꼴(M,A,B) - 부채꼴(S,A,B)
= 원(M) + 사각형(M,A,S,B) - 부채꼴(M,A,B) - 부채꼴(S,A,B)

이제 주어진 정보를 가지고 원과 부채꼴, 삼각형을 구하면 문제를 해결할 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다. Close Spoiler

원과 부채꼴, 삼각형의 넓이를 구하는 공식은 다음과 같습니다.

원의 넓이 = πr²
부채꼴의 넓이 = 1/2r²θ
삼각형의 넓이*2 = 1/2ah * 2 = ah

하지만 주어진 정보로는 원의 넓이 π * m * m 는 구할 수 있지만
부채꼴의 넓이를 구하는 공식 1/2 * m * m * θ₁ 과 1/2 * s * s * θ₂ 의 각도 θ₁과 θ₂,
사각형의 넓이를 구하는 공식 1/2 * a * h의 밑변 a와 높이 h가 추가적으로 필요합니다.

여기서 필요한 값들을 구하기 위해 위 그림에서 A와 B를 잇는 임의의 선를 추가합니다.

(눈만 아프게 색깔만 늘어나네요.)
해당 선은 위에서 보는 것과 같이 c와 수직으로 만나며, 동일한 길이의 두개의 임의의 선 h로 나누어지며, c를 나눈 임의의 선 c1과 c2로 나누어질 수있습니다.

이제 사각형 M,A,S,B의 넓이는 동일한 넓이를 가지며 밑변이 c, 높이가 h인 두 삼각형 M,A,S와 M,B,S의 넓이의 합으로 구할 수 있습니다.

그리고, 부채꼴의 넓이를 구하기 위한 각도를 구하기 위해서는 사각형을 4등분하고 있는 직각삼각형을 이용하여 삼각함수와 역삼각함수를 이용하여 구할 수 있습니다.

즉, M,A,B로 이루어진 부채꼴의 각도는 asin(h/m)으로 구할 수 있으며, S,A,B로 이루어진 부채꼴의 각도는 asin(h/s)로 구할 수 있습니다.

여기까지 정리하면 다음과 같습니다.

원(M)의 넓이 = π * m * m
사각형(MASB)의 넓이 = (1/2 * s * h) * 2 = s * h
부채꼴(MAB)의 넓이 = 1/2 * m * m * (asin(h/m) * 2) = m * m * asin(h/m)
부채꼴(SAB)의 넓이 = 1/2 * s * s * (asin(h/s) * 2) = s * s* asin(s/m)

이제 미지수는 h밖에 남지 않았네요.

마침, 우리가 알고있는 정보 m, s, c의 세개의 선으로 이루어진 삼각형 MAS가 존재합니다.
그리고 세변의 길이를 알고있을 때 헤론의 공식을 이용하여 삼각형의 넓이를 구할 수 있으며, 이를 밑변 s로 나눈 후 2를 곱하면 높이 h를 구할 수 있습니다.

헤론의 공식은 다음과 같습니다.

위 공식으로 h를 구하면,

msc = (m + s + c) / 2
h = sqrt( msc * (msc - m) * (msc - s) * (msc - c) )

멀리 돌아왔네요.
이제 여기서 구한 공식을 코딩을 통해 구현하면 답을 구할 수 있습니다.

== 소스보기 ==

결과

#

453372

문제

MOON

언어

cpp

길이

333B

수행시간

3ms

결과

정답

제출일

2016-08-05