[C++] 백준 7869 - 두 원 [Gold2]

출처

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

풀이 전략

세 가지 조건으로 나누어서 풀이를 한다.

번호	조건
1	원이 전혀 겹치지 않는 경우
2	원이 일부만 겹치는 경우
3	한 원이 다른 원에 포함되는 경

사실 세 가지 조건이지만, 1번의 경우는 0을 출력하면 되고, 3번의 경우는 반지름이 작은 원의 넓이를 출력하면 되기 때문에 사실상 2번을 구하는 식만 구현하면 된다.
고등학교 수학시간에 많이 나왔던 도형의 넓이를 구하는 문제이지만, 원이 겹치는 넓이를 구해야하기 때문에 은근 까다로울 뿐더러 double 자료형을 써야하기 때문에 신경써야할 부분이 많은 문제이다.

잠시 고등학교 수학 시간으로 돌아가보면, 원의 넓이를 구하는 공식은 2πr2이라는 것은 누구나 다 알 것이다. 그리고 원의 일부인 호의 넓이를 구하는 공식은 21​r2θ 이기 떄문에 호의 넓이에서 두 원의 교점을 이은 직선으로 둘러싸인 삼각형의 넓이를 빼는 전략으로 접근을 할 것이다.

풀이

세 가지 경우가 있다. (사실 2가지 이지만ㅎ)
첫 번째 원은 문제의 예시, 오른쪽에 있는 두 번째 원은 일반적으로 두 원이 겹치는 경우, 제일 아래 있는 세 번째 원은 한 원이 다른 원에 포함되는 경우이고 두 원이 겹치지 않는 경우는 너무나도 당연하기 때문에 그리지 않았다.

먼저 그나마 간단한 한 원이 다른 원에 포함되는 경우는 r1과 r2 중 어느 반지름이 더 큰지는 입력값에 따라 달라지기 때문에 또 여러 가지 조건으로 나누어주어야 한다. 이를 조금 더 간단히 구현하기 위해 Swap 함수를 이용하여 r1보다 r2가 클 때 두 반지름을 바꿔서 무조건 r2가 r1보다 작게 만들어준 뒤 원을 구하는 공식​으로 원의 넓이를 구하도록 구현을 했다.

두 번째로 두 원이 겹치는 경우는, 조금 복잡하다.
풀이 전략에서 말했듯이 호의 넓이에서 두 원의 교점을 지나는 직선으로 둘러싸인 삼각형을 빼주는 전략으로 갈건데 넓이를 구하기 전에 구해야 할 것이 있다.

1. 두 원의 중심 사이의 거리
2. 호의 중심각

두 원의 중심사이의 거리는 두 좌표사이의 거리를 구하는 공식을 이용해서 구할 것이고, 호의 중심각은 제2코사인의법칙을 이용할 것이다.

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

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

이런 삼각형이 주어졌을 때, 각BAC를 구하고자 한다면, 각을 마주보고 있는 직선인 a의 제곱은 각을 끼고 있는 두 직선 b,c의 각각의 제곱에서 b,c의 내적값을 2배 해준 값을 빼준 것과 같다는 이론이다.

소스 코드

/*
# Question: BJ7869 (https://www.acmicpc.net/problem/7869)
# Rank: Gold2
# Algorithm: Math, Geometry, Many Conditions
*/

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void Swap(double &a, double &b){
    double temp = a;
    a = b;
    b = temp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    double x1, y1, r1, x2, y2, r2;
    double dist, result, theta1, theta2, S1, S2;
    double PI = 3.14159265358979f;
    
    cin>>x1>>y1>>r1>>x2>>y2>>r2;
    cout<<fixed;
    cout.precision(3);

    dist = sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    // 제2코사인 법칙
    // r2를 작은 원으로 만들어 주기
    if(r1<r2){
        Swap(r1,r2);
        Swap(x1,x2);
        Swap(y1,y2);
    }

    // 1. 두 원이 전혀 겹치지 않는 경우
    if(dist >= r1+r2){
        result = 0.000;
    }
    // 2. 한 원이 다른 원에 포함될 경우
    else if(dist+r2 <= r1){
        result = r2 * r2 * PI;
    }
    // 3. 겹치는 영역이 있는 경우
    else{
        theta1 = acos((r1*r1+dist*dist-r2*r2)/(2*r1*dist));
        theta2 = acos((r2*r2+dist*dist-r1*r1)/(2*r2*dist));
        S1 = (r1*r1*theta1)-r1*r1*sin(2*theta1)/2;
        S2 = (r2*r2*theta2)-r2*r2*sin(2*theta2)/2;
        result = S1 + S2;
    }

    cout<<result<<"\n";
    return 0;
}

double 형이라 int형을 다룰때 보다 복잡해서 원의 넓이를 구하는 과정을 따로 함수를 만들어서 코드를 좀 깔끔하게 하려고했는데 자꾸 오류가 나서 그냥 main 함수에 다 때려박아놨다.
그리고 cmath library를 불러와서 pow함수를 쓰는 것도 고려해보았는데 이또한 그냥 구했다.

결과

결론

세상의 모든 자료형이 int형이였으면...