CirclesCountry

문제

x1, y1 에서 x2, y2 로 이동하려 한다.

지역들은 모두 원으로 표현되어 있으며
지역의 경계가 겹치거나 접하는 일은 없다

지역 i 의 중심은 X[i], Y[i], 반경은 R[i] 로 표현된다

출발점과 도착점은 지역의 경계에 있지 않다

이동할때 지나는 최소 경계수를 리턴

예시 입력

{0},
{0},
{2},
-5, 1,
5, 1

{0, -6, 6},
{0, 1, 2},
{2, 2, 2},
-5, 1,
5, 1

{1, -3, 2, 5, -4, 12, 12},
{1, -1, 2, 5, 5, 1, 1},
{8, 1, 2, 1, 1, 1, 2},
-5, 1,
12, 1

{-3, 2, 2, 0, -4, 12, 12, 12},
{-1, 2, 3, 1, 5, 1, 1, 1},
{1, 3, 1, 7, 1, 1, 2, 3},
2, 3,
13, 2

{-107, -38, 140, 148, -198, 172, -179, 148, 176, 153, -56, -187},
{175, -115, 23, -2, -49, -151, -52, 42, 0, 68, 109, -174},
{135, 42, 70, 39, 89, 39, 43, 150, 10, 120, 16, 8},
102, 16,
19, -108

예시 출력

0
2
3
5
3

생각의 변화

그래프 화
무엇을 간선으로 하고, 무슨 일을 할까

가야하는가, 조건

현재 점이 원 안에 있는지 체크하는 식은

그래프 표현 구조는
표현해야 할까

같은 원 안에 있으면 무시
다른 원 안에 있으면

원을 순회하며 체크
둘 다 밖에거나 둘 다 안이면 무시
그 외엔 +1

pseudo code

double getDistance(int x1, int y1, int x, int y)
    // return sqrt(pow(x1 -x, 2) + pow(y1 - y, 2))
    return hypot(x1 -x, y1 -y)
    
leastBorders(X, Y, R, x1, y1, x2, y2)
    ret = 0
    n = X.size()
    
    for i=0  i<n  i++
        dist1 = getDistance(x1, y1, X[i], Y[i])
        dist2 = getDistance(x2, y2, X[i], Y[i])
        
        if dist1 < R[i]  &&  dist2 < R[i]
        
        else if dist1 > R[i]  &&  dist2 > R[i]
    
        else
            ret++
            
    return ret    

그래프 구조에 대해

트리처럼 보이는 그래프를 그리고, 탐색을 할수는 있다