[C++/백준] 두 원 (No. 7869)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 삼각형의 선분과 사잇각에 대해 알고 있으면 쉽게 풀 수 있는 문제다.

 

처음에 직접 교점의 좌표를 구해서 풀어야 하나? 생각이 들었지만, 다시 생각해보니 r1, r2, 두 원점사이의 거리를 알고 있기 때문에 쉽게 풀 수 있겠다는 생각이 들었다.

 

아래 그림을 보며 어떻게 경우를 분류할지 생각해보자

 

먼저 아래 경우는 두 원이 겹치지 않는 경우다.

 

중점사이의 거리 d가 r1+r2보다 크거나 같으면 두 원은 겹치는 적이 없다.

 

아래는 두 원 중 한 원이 다른 원에 포함되는 경우다.​

 

두 원 중 큰 원의 반지름 r1의 값이 [중점 사이의 거리 d] + r2 보다 크다는 사실을 알 수 있다.

 

위 두 경우를 제외하면 나머지는 두 원이 겹치는 면적을 계산해 주어야 한다.

 

계산하는 방법은 간단하다 두 원에 대해  부채꼴의 넓이에서 삼각형의 넓이를 빼주면 된다.

그리고 빨간색 원에 대해서도 겹치는 넓이를 구하기 위해서는 부채꼴에서 삼각형의 넓이를 빼주면된다.

 

그러면 두 부채꼴에 대해 빼주어야 하는 부분의 넓이를 아래와 같이 표시할 수 있다.

빼주어햐 하는 부분의 넓이는 [두 원 중점의 거리] * [만나는 두 점의 길이] / 2 가 된다.

 

그러면 [두 부채꼴의 넓이] - [두 원 중점의 거리] * [만나는 두 점의 길이] / 2 가 정답이 된다.

 

마찬가지로 한 원의 각이 180도를 넘어가는 경우에도 똑같은 방법으로 구할 수 있다.

 겹치는 부분의 넓이를 보면 초록색 부분과 파란색 부분의 합이다.

여기서 파란색은 부채꼴의 넓이이고, 초록색의 넓이는 빨간색 부채꼴 - [두 원의 중점사이의 거리] * [두 교점의 길이] / 2가 성립한다.

 

그러므로 180도가 넘어가는 경우에도 같은 방법으로 겹치는 부분의 넓이를 계산할 수 있다.

 

+ 여기서 부채꼴의 넓이를 계산하는 방법은 삼각형의 세 변의 길이를 이용해 각도를 구한 다음 부채꼴의 넓이를 구했다.

 $$ r2^2=d^2+r1^2-r1*d*cos(\theta)$$

를 이용하면 각도를 구할 수 있고 이를 이용해 부채꼴의 넓이를 구할 수 있다.

 

 

 

[아이디어 정리]

1. 두 원의 중점사이의 거리를 계산한다.
2. 중점사이의 거리를 이용해 두 원이 겹치는지, 겹치지지 않는지, 한 원이 다른 원을 포함하는지 계산한다.
3. 두 원이 겹치는 경우라면, 삼각형의 세 변의 길이를 이용해 사잇각을 계산하고, 부채꼴의 넓이를 구한다.
4. 이후 두 부채꼴의 넓이 - [두 원의 중점사이의 거리] * [두 교차점의 거리] / 2 가 겹치는 부분의 넓이이다.

 

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;

const long double PI = acos(-1);
int main() {
    long double x1, y1, r1, x2, y2, r2;
    long double tmp;
    cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
    if (r1 < r2) { //항상 r1이 더 큰 원이 되도록 한다.
        tmp = x1, x1 = x2, x2 = tmp;
        tmp = y1, y1 = y2, y2 = tmp;
        tmp = r1, r1 = r2, r2 = tmp;
    }
    long double cDist = (y2 - y1)*(y2-y1) + (x2 - x1)*(x2-x1); // 제곱 값
    long double cDistR = sqrt(cDist); //중점사이의 거리
    long double smallSize,largeSize;
    cout << fixed;
    cout.precision(3);
    if (cDistR > r1 + r2) { //겹치지 않는다면
        cout << 0.000f;
    }
    else if (cDist  <= (r1 - r2)*(r1-r2)) //두 원이 완전 포함되는 경우라면
    {
        cout << PI * r2 * r2;
    }
    else
    {
        long double bigCosT = (r1 * r1 + cDistR*cDistR - r2 * r2) / (2 * r1 * cDistR);
        long double bigTheta = acos(bigCosT);
        long double bigSinT = sin(bigTheta);
        long double distH = 2*r1 * bigSinT;
        long double smallCosT = (r2 * r2 + cDistR * cDistR - r1 * r1) / (2 * r2 * cDistR);
        long double smallTheta = acos(smallCosT);
        cout << (r1 * r1 * bigTheta) + (r2 * r2 * smallTheta) - (distH * cDistR / 2);
    }
        

    return 0;
}

 

---

왜 틀렸는지 몰라서 정말 3시간 동안 고민했던 문제다.

알고보니 겹치지 않는 경우 넓이를 0으로 출력했는데, 0.000f로 출력해야 정답이었다.

 

정말 어처구니 없는 이유로 인해 시간을 날려먹었다;;

 

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