[알고리즘][Python] 백준(BOJ) 1004 어린 왕자_파이썬

 

1004 어린 왕자    https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

 

 

 

 

 

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 원과 점의 관계(수학)

 

 

 

 

 

 

 

풀이 1

<내용>

출발점과 도착점이 원 안에 속하면 진입이나 이탈이 필요하다.

따라서 출발점과 도착점 각각 원 안에 속하는지 확인을 해야 하며 둘 다 속하면 진입이나 이탈을 할 필요가 없다는 점을 이해해야 한다.

flag를 통해 출발점과 도착점이 동시에 속하는 경우를 구별했다.

 

 

<코드>

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x1, y1, x2, y2 = map(int, input().split(' '))
    n = int(input())
    planet = 0
    for _ in range(n):
        flag = True
        cx, cy, r = map(int, input().split(' '))
        dist1 = (cx-x1)**2 + (cy-y1)**2
        if dist1 < r**2:
            planet += 1
            flag = False
        dist2 = (cx-x2)**2 + (cy-y2)**2
        if dist2 < r**2:
            if flag:
                planet += 1
            else:
                planet -= 1
            
    print(planet)

 

 

+) flag를 통하지 않고

• 출발점과 도착점이 모두 원에 속할 때
• 출발점이 원에 속하고 도착점은 속하지 않을 때
• 출발점은 원에 속하지 않고 도착점은 원에 속할 때
• 출발점과 도착점 모두 원에 속하지 않을 때

로 구분해서 하는 방법 코드화 해보자.

 

 

 

 

 

풀이 2

<내용>

• 출발점과 도착점이 모두 원에 속할 때
• 출발점이 원에 속하고 도착점은 속하지 않을 때
• 출발점은 원에 속하지 않고 도착점은 원에 속할 때
• 출발점과 도착점 모두 원에 속하지 않을 때

로 구분하여 출발점 또는 도착점이 속하지만 둘 다 속하지 않는 속성을 이용하면 된다.

만약 출발점이 속할 경우 dist1 < 0, 도착점이 속할 경우 dist2 < 0이므로

dist1 * dist2가 0보다 작으면 출발점, 도착점 중 하나만 속하는 경우이므로 진입이나 이탈이 필요하다.

 

 

<코드>

t = int(input())
for _ in range(t):
    cnt = 0
    x1, y1, x2, y2 = map(int, input().split())
    n = int(input())
    for _ in range(n):
        cx, cy, r = map(int, input().split())
        dist1 = (((x1 - px) ** 2) + ((y1 - py) ** 2)) ** 0.5 - r
        dist2 = (((x2 - px) ** 2) + ((y2 - py) ** 2)) ** 0.5 - r
        if dist1 * dist2 < 0:
            cnt += 1
    print(cnt)

 

 

 

 

 

 

 

 

복습

<내용>

import sys
input = sys.stdin.readline
input()

sys를 import 해서 할 경우 위와 같이 설정할 때,

input = sys.stdin.readline()을 하면

밑의 코드 input()이 sys.stdin.readline()()이므로 런타임 오류가 발생함을 주의하자!