[백준 1004] 어린왕자

 

www.acmicpc.net/problem/1004

1004번: 어린 왕자

import sys
import math
from collections import deque
input = sys.stdin.readline

T = int(input())

def is_in(p,x,y):
    cx,cy,r = p
    len_x = abs(x-cx)
    len_y = abs(y-cy)


    rg = math.sqrt(len_x**2 + len_y**2)

    if rg <= r:
        return True
    return False


def min_in_out(sx,sy,es,ey,planets):
    cnt = 0

    for p in planets:
        if is_in(p,sx,sy) and not is_in(p,es,ey):
            cnt+=1
        elif not is_in(p,sx,sy) and is_in(p,es,ey):
            cnt+=1
    return cnt


for _ in range(T):
    sx,sy,es,ey = map(int,input().split())
    n = int(input())
    planets = [list(map(int,input().split())) for i in range(n)]

    answer = min_in_out(sx,sy,es,ey,planets)
    print(answer)
    

풀이

다양한 방법으로 풀 수 있을 것 같은데 나는 아래와 같이 생각했다.

 

일단 한 원이 있다고 하자.

이 원안에 시작점과 끝점이 둘 다 존재하면 둘 사이에 경계가 없다.

또한 시작점과 끝점 둘 다 밖에 존재하면 둘 사이에 경계가 없다.

즉 시작점과 끝점 둘 중 하나만 안에있고 하나는 밖에 있을 때 경계가 생긴다.

 

점이 원 안에 존재하는지 체크하는 방법은 피타고라스 정리를 사용한다.

 

시작점 or 도착점 둘 중 하나만 포함되는 경우는 cnt+=1

cnt가 답이된다.

시간복잡도

원의 수만큼 로직을 돌리면 되기때문에 O(N)이다.