[백준] 1004_어린왕자

목차

🔐문제 풀이

시행착오

두 점 간의 거리 구하는 공식은 다음과 같다

이 공식을 응용하여 문제를 풀었다.

- 만약 두 점 사이의 거리가 반지름 보다 작다면, 점이 원 안에 포함되어 있다

- 따라서, 거리가 반지름 보다 작다면 cnt를 중가시켜, 총 개수를 구한다

- point 0과 point1, point2와 point3은 세트 이므로, 다음과 같이 작성한다

import sys

def isIn(points , x,y,r):
    cnt = 0
    for i in range(0,4,2): #0,2
        if ((points[i]-x)**2 + (points[i+1]-y)**2)<r**2:
            cnt+=1
    return cnt

test_num = int(sys.stdin.readline())

for test in range(test_num):
    cnt = 0
    points = list(map(int, sys.stdin.readline().split()))
    planet_cnt = int(sys.stdin.readline())

    for i in range(planet_cnt):
        x,y,r = map(int, sys.stdin.readline().split())
        cnt+=isIn(points, x,y,r)

처음에는 위에와 같은 방식으로 풀었는데, 백준 테스트 결과 계속 틀렸다고 했다,,,

뭐가 문제인지 너무 모르겠어서 질문게시판 을 참조하던 중, 이 글을 발견하게 되었다!

알고보니, 두 점이 같은 원 안에 존재할 경우를 고려하지 않았던 것!

수정된 로직은 다음과 같다

- 만약 점 A와 점 B의 거리가 모두 반지름 보다 작다면, 같은 원안에 있는것이기 때문에, cnt를 증가시키지 않는다

- 이외에는 위와 동일.

 

문제 풀이

import sys

def isIn(points , x,y,r):
    cnt = 0  
    start_dist = (points[0]-x)**2+(points[1]-y)**2
    end_dist = (points[2]-x)**2+(points[3]-y)**2

    # 두 점이 같은 원안에 들어있을 경우 제외
    if start_dist < r**2 and end_dist < r**2:
        pass
    elif start_dist < r**2 or end_dist < r**2:
        cnt+=1
    return cnt


test_num = int(sys.stdin.readline())

for test in range(test_num):
    cnt = 0
    points = list(map(int, sys.stdin.readline().split()))
    planet_cnt = int(sys.stdin.readline())

    for i in range(planet_cnt):
        x,y,r = map(int, sys.stdin.readline().split())
        cnt+=isIn(points, x,y,r)