사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
L Y​ M Y J
 
ps/problems/boj/7869.txt · 마지막으로 수정됨: 2022/02/17 09:00 저자 teferi