반응형
문제 출처 :
https://www.acmicpc.net/problem/1004
알고리즘 분석 :
문제 해결에 필요한 사항
1. 구현
좋은 풀이를 생각하고자 다양한 사람들의 글을 찾아본 결과 아래 내용이 가장 와닿는 글이므로 이 글로 대체합니다.
어떤 경우에 반드시 원을 지나야 하는지를 찾아내는 것이 핵심이다.
반드시 지나야 하는 경우와, 지나지 않아도 되는 경우를 나눠보면 아래와 같다.
특정 점이 원 내부에 있는지 판별하는 방법은 아래와 같다.
거리 공식은 흔히 사용하는 유클리디언 거리를 사용하였다.
위를 바탕으로 모든 원들에 대해서 지나야 되는지 여부를 검사한 뒤, 지나야 되는 원의 개수를 출력해주면 된다.
소스 코드 :
test_cnt = int(input())
for test in range(test_cnt):
x1, y1, x2, y2 = map(int,input().split())
n = int(input())
count = 0
for i in range(n) :
cx, cy, r = map(int,input().split())
dist1 = ((x1 - cx) ** 2 + (y1 - cy) ** 2) ** (1 / 2)
dist2 = ((x2 - cx) ** 2 + (y2 - cy) ** 2) ** (1 / 2)
if (dist1 < r < dist2) or (dist2 < r < dist1):
count += 1
print(count)
// This source code Copyright belongs to Crocus
// If you want to see more? click here >>반응형