ps:problems:boj:7869
두 원
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 7869 |
문제명 | 두 원 |
레벨 | 골드 3 |
분류 |
수학, 기하 |
시간복잡도 | O(1) |
사용한 언어 | Python |
제출기록 | 32972KB / 68ms |
최고기록 | 60ms |
해결날짜 | 2022/02/17 |
풀이
- 그냥 수학문제.
- 우선 엣지 케이스들부터 따로 처리해주자. 중점사이의 거리 d 가 d≥r1+r2 이어서 겹치는 부분이 0인 경우와, d≤abs(r1-r2)여서 한 원이 다른 원 안에 포함되는 경우이다.
- 이제 일반적인 경우에서는 두 원은 두 점에서 만나고, 두 점을 잇는 선분을 그려서 겹치는 부분을 나누면, 두개의 활꼴의 합으로 계산 가능하다.
- 활꼴은 부채꼴에서 삼각형을 빼주면 구할수 있고, 부채꼴과 삼각형의 넓이는 둘다 반지름과 사이각만 알면 쉽게 구할수 있다.
- 사이각을 구하는 것은.. 중점에서 현까지의 길이 l을 구해서, acos(l/r)로 계산하는 것이 내가 처음 푼 방식이긴 한데.. 현에 해당하는 직선의 방정식을 구하고 점과직선과의 거리 공식에 대입해서 구하려면 좀 번거롭고, 사이각이 180도 보다 더 큰지 아닌지를 다시 위치관계를 보고서 처리해야 하는 것도 있다.
- 더 간단한 방식은 그냥 코사인 법칙을 쓰는 것. 교점 한개와,두 원의 원점을 갖고 삼각형을 그리면, 세 변의 길이를 모두 아니까 바로 구할수 있고, 사이각이 예각인지 둔각인지도 바로 구별된다.
- 우연히 검색해보다가 알았는데 요즘에는 이것을 제2코사인 법칙이라고 안 부르고, 그냥 코사인법칙이라고 배운다고 한다. 이런것도 바뀌는구나..
- 이제 그럼 그대로 계산해주면 끝. 시간복잡도는 O(1)이다.
코드
"""Solution code for "BOJ 7869. 두 원".
- Problem link: https://www.acmicpc.net/problem/7869
- Solution link: http://www.teferi.net/ps/problems/boj/7869
Tags: [Math] [Geometry]
"""
import math
def main():
x1, y1, r1, x2, y2, r2 = [float(x) for x in input().split()]
d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
if r1 + r2 <= d:
answer = 0
elif d <= abs(r1 - r2):
answer = math.pi * r1 * r1 if r1 <= r2 else math.pi * r2 * r2
else:
theta1 = 2 * math.acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d))
theta2 = 2 * math.acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d))
area1 = r1 * r1 * theta1 / 2 - r1 * r1 * math.sin(theta1) / 2
area2 = r2 * r2 * theta2 / 2 - r2 * r2 * math.sin(theta2) / 2
answer = area1 + area2
print(f'{answer:.3f}')
if __name__ == '__main__':
main()
ps/problems/boj/7869.txt · 마지막으로 수정됨: 2022/02/17 09:00 저자 teferi
토론