일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 그리디
- BOJ
- 유니온파인드
- stack
- 동적계획법
- Greedy
- 종만북
- 알고스팟
- 백준
- 이분탐색
- 세그먼트트리
- 스택
- 너비우선탐색
- acm
- BFS
- 알고리즘문제해결전략
- 문자열
- priority_queue
- 완전탐색
- DP
- union-find
- DFS
- backtracking
- 재귀
- 분할정복
- 분리집합
- Algospot
- 누적합
- 백트래킹
- 다이나믹프로그래밍
- Today
- Total
DAMPER's 낙서장
7869. 두 원 본문
https://www.acmicpc.net/problem/7869
문제 설명
두 원이 주어졌을 때, 두 원이 교차하는 영역의 넓이를 소수점 셋째자리까지 구하면 된다.
solve
문제에서 제시하는 조건은 각 원의 중심 좌표와 반지름이다.
코사인 법칙을 활용해 문제를 해결할 수 있다.
먼저 두 원의 위치를 파악한다.
두 원의 중심을 잇는 선분을 긋고 이 선분의 길이를 d라고 하자.
1. 두 원이 멀리 떨어져 교차하는 영역이 없는 경우. ( d > r1 + r2)
2. 두 원이 외접하는 경우 ( d = r1 + r2)
3. 두 원이 교차하지만 어느 한 원이 다른 원에 포함되어있지는 않은 경우. (d < r1 + r2)
4. 어느 한 원이 다른 원 안에 존재하는 경우. (r1 + d > r2 or r2 + d > r1)
5. 두 원이 내접하는 경우. (r1 + d = r2 or r2 + d = r1)
1번과 2번은 두 원이 교차하는 부분이 없으므로 0을 출력하면 된다.
4번과 5번은 두 원중 작은 원이 다른 한 원 안에 포함되어있는 경우이기 때문에 작은 원의 넓이를 출력하면 된다.
문제는 3번이다.
이 상황에서 문제를 해결하기 위해서는 제2코사인법칙에 대한 지식이 필요하다.
https://ko.wikipedia.org/wiki/%EC%BD%94%EC%82%AC%EC%9D%B8_%EB%B2%95%EC%B9%99
우리는 두 원의 거리와 두 원의 반지름을 알고 있기 때문에, 이를 기반으로 삼각형을 만들면 이 삼각형의 각에 대한 정보를 알 수 있다.
먼저 코사인법칙에 대해 언급하면
세 각이 \( A, B, C \) 이고 마주하는 변을 \(a, b, c \) 라고 했을 때, \( c^2 = a^2 + b^2 - 2abcosC \) 가 성립한다.
두 원의 중심을 잇고, 원의 중심과 원들이 만나는 점을 이으면
두 원의 중심거리과 반지름으로 이루어진 삼각형 두 개를 만들 수 있다.
이 삼각형에 코사인법칙을 적용하면 교차하는 각 원의 부채꼴의 중심각을 알 수 있다.
\( cosC = \frac{(a^2 + b^2 - c^2)}{2ab} \) 이므로 \( C = arccos(\frac{(a^2 + b^2 - c^2)}{2ab}) \) 이다.
\(C\)는 부채꼴의 중심각의 반으로 두면 \(2C\)를 구하면 중심각을 알 수 있다.
두 원이 교차하는 넓이는
두 부채꼴의 넓이 합 - 부채꼴에 포함된 부분의 삼각형의 넓이의 합을 계산한 결과이다.
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a, b) (a) ^= (b) ^= (a) ^= (b)
#define endl '\n'
#define int long long
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
class circle
{
public:
double x, y, r;
circle() {}
circle(double x, double y, double r)
{
this->x = x;
this->y = y;
this->r = r;
}
};
double getDist(circle a, circle b)
{
return sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));
}
bool equals(double a, double b)
{
return fabs(a - b) < EPS;
}
int32_t main()
{
cin.sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
cout.precision(3);
cout << fixed;
circle c[2];
for (int i = 0; i < 2; i++)
{
cin >> c[i].x >> c[i].y >> c[i].r;
}
double dist = getDist(c[0], c[1]);
if (dist > c[0].r + c[1].r || equals(dist, c[0].r + c[1].r))
{
cout << 0.000;
return 0;
}
if (fabs(c[0].r - c[1].r) >= dist)
{
cout << PI * min(c[0].r * c[0].r, c[1].r * c[1].r);
return 0;
}
double theta1 = 2.0 * acos((c[0].r * c[0].r + dist * dist - c[1].r * c[1].r) / (2.0 * c[0].r * dist));
double theta2 = 2.0 * acos((c[1].r * c[1].r + dist * dist - c[0].r * c[0].r) / (2.0 * c[1].r * dist));
double ans = c[0].r * c[0].r * theta1 / 2.0 + c[1].r * c[1].r * theta2 / 2.0;
ans -= c[0].r * c[0].r * sin(theta1) / 2.0;
ans -= c[1].r * c[1].r * sin(theta2) / 2.0;
cout << ans;
return 0;
}
|
cs |
'Problem Solving > BOJ 문제풀이' 카테고리의 다른 글
11780. 플로이드 2 (0) | 2022.07.09 |
---|---|
3015. 오아시스 재결합 (0) | 2022.07.09 |
1509. 팰린드롬 분할 (0) | 2022.07.04 |
1007. 벡터 매칭 (0) | 2022.07.04 |
13140. Hello World! (0) | 2022.01.13 |