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()
ps/problems/boj/1004.txt · 마지막으로 수정됨: 2022/02/24 16:42 저자 teferi
토론