[백준 1004 실버3] 어린 왕자

www.acmicpc.net/problem/1004

1004번: 어린 왕자

해결방안

• 점과 점 사이의 거리를 이용한 방식 사용

• 점과 점 사이 거리 공식을 알아야 풀 수 있음

알고리즘

1. 두 점 사이의 거리를 구하는 공식과 반지름의 길이 비교하는 함수 정의

2. 출발점(x,y), 도착점(x,y) 입력 받음
3. x, y, 반지름 값을 튜플로 받아 리스트에 저장
4. 리스트에서 값을 하나씩 돌면서 출발점과, 도착점, 값을 함수에 넣어서 비교
   1. 출발점과 도착점이 모두 원 안에 있는 경우, 카운트 하지 않고 continue
   2. 둘 중 하나만 원 안에 존재하는 경우, 카운트 증가
5. 종료 시, 카운트 값 출력

핵심 팁

• 그림을 보고 복잡하다고 너무 긴장하지 말 것!
• 두 점 사이의 거리가 반지름 보다 작다면 좌표는 원 안에 존재하는 것, 아니라면 원 밖에 존재
  • 즉, 원 안에 존재한다면 진입/이탈 횟수 카운트 할 필요 없음
  • 원 밖에 존재할경우 1씩 카운트
• 점들의 위치에 따라 나올수 있는 경우를 고려해야 함
  1. 두 점이 원 안에 있는 경우
     • 값이 카운트 되지 않아야 함
  2. 한 점이 원 안에 있는 경우
     • 값이 카운트 되어야 함
  3. 두 점 모두 원 밖에 있는 경우
     • 값이 카운트 되지 않아야 함
• 처음에 실수한 이유
  1. 두 점이 원 안에 동시에 들어왔을 경우 break하고 0출력
     • 반례) 이전에 동시에 들어오지 않고, 이후에 원 안에 동시에 들어왔을 경우, 이미 카운트 할 수 있으므로 0 출력하면 틀림
     • 수정안) 반지름의 길이를 기준으로 오름차순으로 정렬 후, 두 점이 원 안에 동시에 들어오는 경우 break하고 카운트값 출력
  2. 두 점이 원 안에 동시에 들어오고, 이전에 카운트 한 값이 없을 경우, break
     • 반례) 위의 사항과 마찬가지로 이전에 카운트 한 값이 존재하고, 이후에 원 안에 동시에 들어오는 경우 가능, 그러므로 이전에 카운트 한 값이 없는 경우를 체크하지 못하므로 break는 불가하고, 오히려 다음 구문에서 카운트만 늘어남 
     • 수정안) 원 안에 동시에 들어오는 경우, continue를 이용해 건너뜀

 

 

 

import math
# 안에 있다면 True 리턴
# 안에 없다면 False 리턴
def check(x, y, dx, dy, rr):
    nx = abs(x - dx)
    ny = abs(y - dy)
    if rr - math.sqrt(((nx * nx) + (ny * ny))) > 0:
        return True
    else:
        return False
t = int(input())
for _ in range(t):
    sx, sy, ex, ey = map(int, input().split())
    n = int(input())
    circles = list()
    # 반지름이 가장 작은것부터 오름차순으로 정렬
    for _ in range(n):
        x, y, r = map(int, input().split())
        circles.append((x, y, r))
    # 현재는 굳이 정렬안해도 성공
    circles.sort(key=lambda x: x[2])
    # 체크하기 위한 플래그
    f_in = False
    in_check = 0

    for a, b, c in circles:
        start_check = check(sx, sy, a, b, c)
        end_check = check(ex, ey, a, b, c)
        # 한개는 안에 있는게 먼저 나오고, 그 다음번에 둘다 안에 있는게 나올 경우,
        # in_check가 증가하지 말아야 하는데, 아래와 같은 조건에서는 1 증가함
        # if in_check == 0 and start_check is True and end_check is True:
        #     f_in = True
        #     break
        if start_check is True and end_check is True:
            continue
        elif start_check is True or end_check is True:
            in_check += 1
    print(in_check)

 

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public