기하 알고리즘] 두 원의 겹치는 영역의 넓이 구하기

위의 그림과 같이 x1,y1,r1/ x2,y2,r2 가 주어진 경우 겹치는 영역의 넓이를 구하는 방법에 대해 살펴 보도록 하겠습니다.

두 원의 중심과 중심 사이의 거리 d는 피타고라스의 정리에 의해서 

d * d = (x1-x2) * (x1-x2) + (y1-y2)*(y1-y2) 가 됩니다.

여기서 부채꼴의 넓이를 구하는 공식을 살펴 보자.

S(부채꼴의 넓이) = πr² * ^x/₃₆₀ 으로 구할 수 있다.

각도를 θ/2π 와 같이 나타낼 수 있으므로

S(부채꼴의 넓이) = πr² * θ/2π  -------------(1)

여기서 겹치는 영역의 값을 구한다고 하면 다음과 같이 구할 수 있다.

S1(부채꼴 1의 넓이) + S2(부채꼴 2의 넓이)를 먼저 구한다. 

그러면 우리가 구하려고 하는 겹치는 영역의 넓이가 2번 포함된 부채꼴의 합이 된다.

이렇게 구한후 위의 그림과 같이 삼각형 2개의 넓이를 빼 주게 되면 겹치는 영역의 넓이만 남게 된다.

이등변 삼각형의 넓이를 각도를 이용해서 구하는 방법을 살펴 보면 다음과 같다.

 

이 원리에 의해서 

a = c * sinA

b= c*cosA

이므로 

이러한 이등변 삼각형의 넓이를 구하는 방법에 대해 생각해 보자.

θ 를 정확히 2등분하면 θ/2 가 되며 직각이 된다.

여기서 cos(θ/2) = 높이/r 이 된다.

따라서 높이 = r * cos(θ/2) 

sin(θ/2) = (밑변/2)/r 로 나눈 값이므로

밑변 = r * sin(θ/2) * 2

따라서 삼각형의 넓이 =  높이 * 밑변 / 2이므로

r * cos(θ/2) * r * sin(θ/2) * 2 / 2

이렇게 나온것을

삼각함수의 성질

sinθ1cosθ2 = (sin(θ1+θ2) +sin(θ1-θ2))/2

θ1 == θ2 이므로

sin(θ/2)cos(θ/2) = (sin(θ) + sin(0))/2 = sin(θ)/2 로 간소화 할 수 있다.

따라서 r * cos(θ/2) * r * sin(θ/2) * 2 / 2 = r * r * sin(θ/2 * 2)/2 = r * r * sin(θ)/2 

삼각형 면적은 r * r * sin(θ)/2  -------------(2)

이렇게 하면 각도 θ 만 구하면 위의 식에 의해서 겹치는 부분의 면적을 구할 수 있다.

 

다음으로 각도를 구하기 위해 코사인 법칙을 살펴 보자.

참고 : https://ko.wikipedia.org/wiki/%EC%BD%94%EC%82%AC%EC%9D%B8_%EB%B2%95%EC%B9%99

코사인 법칙 - 위키백과, 우리 모두의 백과사전

a² = b² + c² - 2bc(cosA)

cosA = (b²+c²-a²)/2bc

와 같이 나타낼 수 있으므로 다음과 같은 형식으로 왼쪽 원 θ1 를 구할 수 있다.

cos(θ1/2) = (r1² + d² - r2²)/(2*r1*d)

θ1/2 = cos^-1 * ((r1^2 + d^2 - r2^2)/(2*r1*d))

오른쪽 원 θ2는 같은 방법으로

cos(θ2/₂) = (r2² + d² - r1²)/(2*r2*d)

θ2/2 = cos^-1 * ((r2² + d² - r1²)/(2*r2*d))

으로 구할 수 있다.

이렇게 각도를 찾아 내면 공식에 의해 a,b,c 및 각도에 의한 부채꼴의 넓이 등을 계산 할 수가 있다.

 

이러한 두 원의 영역을 구하는 알고리즘 문제인 백준 7869번의 두 원의 문제를 풀어 보자.

https://www.acmicpc.net/problem/7869

7869번: 두 원

 

#include <bits/stdc++.h>


using namespace std;

int main()
{
    double x1,y1,r1,x2,y2,r2;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    constexpr double pi = acos(-1);

    double d = sqrt( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));

    double res = 0;
    if(r1+r2<=d) ///영역이 없다.
        res = 0;
    else if(abs(r1-r2)>=d) ///큰원에 작은원이 포함된 경우
    {
        res = pi * min(r1,r2) * min(r1,r2); ///작은 원의 넓이
    }
    else{
        double theta1 = acos( (r1*r1 + d * d - r2 * r2)/(2*r1*d) );
        double theta2 = acos( (r2*r2 + d*d - r1*r1)/(2*r2*d));

        double s1 = (r1 * r1 * theta1) - (r1 * r1 * sin(2*theta1)/2); ///부채꼴 넓이에서 삼각형 넓이를 빼자.
        double s2 = (r2 * r2 * theta2) - (r2 * r2 * sin(2*theta2)/2);
        res = s1 + s2;

    }

    printf("%.3f",res);


    return 0;
}

 

인천 서구 원당컴퓨터학원

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 일반고,과고,영재고,특성화고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학