[PS][BOJ/7869번] 두 원

HwangBBang·2023년 2월 15일
0

Geometry

목록 보기
2/2
post-thumbnail

문제 설명

두 원이 주어졌을 때, 교차하는 영역의 넓이를 소수점 셋째자리까지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다.

출력

첫째 줄에 교차하는 영역의 넓이를 반올림해 소수점 셋째자리까지 출력한다.

문제 분석 과정

주어진 값은 두 원의 중심과 반지름이다. 우선 두 원의 중심을 알고 있으니
두 원의 중심 사이 거리를 구할 수 있다. (점과 점사이의 거리)

두 원의 중심 사이의 거리를 알았다면 두 원의 포지션을 3가지로 나눌 수 있게된다.

Case1. 교집합 면적이 작은원 그 자체인 경우 : |r1-r2|>=d
Case2. 교집합 면적이 없는 경우 : r1+r2<=d
Case3. 그 외의 모든 경우

우선 Case1.의 경우 작은 원이 교집합되는 면적 그 자체이기 때문에 추가적인 계산 없이 작은 원의 넓이를 출력하면 된다.

다음으로 Case2.의 경우 작은 원이 교집합되는 면적이 없기 때문에 0.000 을 출력하면 된다.(한 점에서 만나는 경우도 포함시켰으나 한 점에서 만나는 경우는 두 원이 접하는 경우 이므로 카운팅하지않는다.)

마지막으로 Case3. 의 경우가 가장 일반적인 경우인데 이때의 두 원을 관찰해보자. Case3.의 두 원은 반드시 두점에서 만나게 된다. 이 경우 우리는 각 원의 중심과 반지름 그리고 각 원의 중심 사이 거리를 알 수 있다. 두 원의 중심끼리 선(이하 d)으로 이어보자.
그럼 d를 공유하는 두개의 삼각형이 만들어진다.이때 두 삼각형은 SSS합동이고, 이 두 삼각형의 모든 변의 길이를 우리는 알고 있게된다. 모든 변의 길이를 알고 있으므로 제 2 코사인 법칙을 이용해 각도 또한 알 수있고, 두 삼각형은 합동이므로 두 삼각형을 합친 각도까지 알 수 있다.

교집합을 구하기위해서는 각 원의 부채꼴의 넓이와 선분d 를 공유하는 두 삼각형의 넓이를 알아야한다. (부채꼴 - 삼각형)
삼각형의 넓이는 두 변과 끼인 사잇각을 통해서 구할 수 있다.

위 과정을 거치면 정답을 구할 수 있다.

점과 점사이의 거리

d=(x1x2)2+(y1y2)2d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

제 2 코사인 법칙

cosθ=(r12+d2r22)(2r1d)\cos\theta = (r_1^2 + d^2 - r_2^2) \over (2*r_1*d)
θ=arccos(r12+d2r222r1d)\theta = \arccos({ r_1^2 + d^2 - r_2^2 \over 2*r_1*d})

삼각형의 넓이

S=sin(θ)r122S = {sin(\theta)*r_1^2\over2}

소스코드

import math

x1, y1, r1, x2, y2, r2 = map(float,input().split())
# 두 원의 중심사이 거리
d = math.sqrt(pow(x1-x2,2)+pow(y1-y2,2))

def getS(d,r1,r2):
    # 제2 코사인 으로 사잇각 구하기
    theta = math.acos((pow(r1,2) + pow(d,2) - pow(r2,2)) / (2*r1*d))
    
    s2 = math.sin(2*theta)*pow(r1,2)/2
    s1 = pow(r1,2)*theta
    
    return(s1-s2)

#영역이 없다.
if r1+r2<=d :
    result = 0.000

# 큰원에 작은원이 포함된 경우
elif abs(r1-r2)>=d :    
    result = math.pi * pow(min(r1,r2),2) 
    
else:
    result = getS(d,r1,r2)+ getS(d,r2,r1)  
    



print('%.3f' % result)

소스코드 원본
문제 원본

profile
https://hwangbbang.tistory.com/

0개의 댓글