백준 1004

문제 링크

문제 설명.

좌표평면상에서 두 점(차례대로 x1 y1 x2 y2로 나타냄)과 여러 원들(차례대로 중점의 좌표와 반지름을 x y r로 나타냄)을 주었을 때 두 점을 잊는 직선이 원들을 통과하는 최소 횟수를 구하는 문제.(두 점은 원의 어떤 경계에도 걸치지 않는다. + 원의 경계도 서로 맞닿거나 교차하는 경우도 없다.)

풀이 원리.

푸는 방법은 간단하다. 두 점이 주어지고, 차례대로 원의 중점과 반지름이 주어졌기 때문에 각각의 점이 원의 반지름을 기점으로 더 멀리 있는지, 혹은 더 가까이 있는지를 체크하면 된다.

1. 만약 두 점이 원의 반지름과 각각 멀리/가까이 있으면 이차원 평면상에서 선을 어떻게 긋든지간에 항상 원의 둘레를 통과해야 한다.(점들이 경계에 없기 때문에., 원들이 하나의 원을 둘러쌓는 것 역시 원의 경계가 맞닿지가 않는다는 가정으로 인해 pass)
2. 하지만 그게 아니라면 원을 피해서 선을 그리면 되기 때문에 두 점을 잊는 직선이 원을 통과하지 않는다고 말할 수 있다.

따라서 1번 조건에 부합하는 원의 갯수만 카운트한다면 정답!

풀이 코드

from sys import stdin

cases = int(stdin.readline())

for _ in range(cases):
    x1,y1,x2,y2 = map(int,stdin.readline().strip().split())
    
    result = 0
    for _ in range(int(stdin.readline())):
        x,y,half = map(int,stdin.readline().strip().split())
        half_sq = half**2
        stt_bd = (x-x1)**2 + (y-y1)**2
        end_bd = (x-x2)**2 + (y-y2)**2
        
        if max(stt_bd,end_bd)<half_sq or min(stt_bd,end_bd)>half_sq:
            continue
        result += 1
    
    print(result)

잡담.

추석 연휴에 뭘 쓸까 하다가 간단히 기념비적인 1004번 문제를 풀어보았다.
요즘은 개인 프로젝트를 함과 동시에 예전에 못풀었던 문제를 풀어제끼고 있는데 플레3짜리 문제가 내 속을 썩이고 있다..