사용자 도구

사이트 도구


ps:problems:boj:1004

어린 왕자

ps
링크acmicpc.net/…
출처BOJ
문제 번호1004
문제명어린 왕자
레벨실버 3
분류

기하학

시간복잡도O(T*n)
인풋사이즈T<=?, n<=50
사용한 언어Python
제출기록30860KB / 80ms
최고기록64ms
해결날짜2022/02/24

풀이

  • 발상에 걸린 시간: 매우 짧음 / 구현에 걸린 시간: 매우 짧음
  • 출발점과 도착점이 둘다 원 안에 있거나, 원 밖에 있으면 원을 지나갈 필요가 없다.
  • 따라서, 주어진 원들 중에서 출발점과 도착점중 한개만 원의 내부에 있는 원의 갯수를 세기만 하면 된다.
  • 시간 복잡도는 O(n)

코드

"""Solution code for "BOJ 1004. 어린 왕자".

- Problem link: https://www.acmicpc.net/problem/1004
- Solution link: http://www.teferi.net/ps/problems/boj/1004

Tags: [Geometry]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        x1, y1, x2, y2 = [int(x) for x in sys.stdin.readline().split()]
        n = int(sys.stdin.readline())
        answer = 0
        for _ in range(n):
            cx, cy, r = [int(x) for x in sys.stdin.readline().split()]
            p1 = (x1 - cx) * (x1 - cx) + (y1 - cy) * (y1 - cy) - r * r
            p2 = (x2 - cx) * (x2 - cx) + (y2 - cy) * (y2 - cy) - r * r
            if p1 * p2 < 0:
                answer += 1
        print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
E X G O Y
 
ps/problems/boj/1004.txt · 마지막으로 수정됨: 2022/02/24 16:42 저자 teferi