×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,281,534명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
강현대 : 5000원(busyhuman)

문제 출처 :

 

https://www.acmicpc.net/problem/1004

 

 

 

알고리즘 분석 :


문제 해결에 필요한 사항

1. 구현

 

좋은 풀이를 생각하고자 다양한 사람들의 글을 찾아본 결과 아래 내용이 가장 와닿는 글이므로 이 글로 대체합니다.

 

https://m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=221048019075&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

어떤 경우에 반드시 원을 지나야 하는지를 찾아내는 것이 핵심이다.
반드시 지나야 하는 경우와, 지나지 않아도 되는 경우를 나눠보면 아래와 같다.

특정 점이 원 내부에 있는지 판별하는 방법은 아래와 같다.

거리 공식은 흔히 사용하는 유클리디언 거리를 사용하였다.


위를 바탕으로 모든 원들에 대해서 지나야 되는지 여부를 검사한 뒤, 지나야 되는 원의 개수를 출력해주면 된다.

 

 

 

 

소스 코드 : 

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