Posts List


2016년 8월 5일 금요일

[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

    댓글 없음:

    댓글 쓰기