테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 어린 왕자 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}