사막 탐험

면접 대비

시간 제한1초메모리 제한512 MB

요약
시작점과 보물, 원형 오아시스 하나가 주어질 때 오아시스 내부 이동이 무료인 상황에서 필요한 최소 유클리드 이동 거리를 구한다.
난이도

보통10점 중 5점

유형
기하, 수학, 그리디, 구현
정답자
아직 제출이 없습니다

문제

성우는 보물을 찾기 위해 사막에 갔다. 사막은 2차원 평면으로 나타낼 수 있다. 성우는 지금 (a_x,a_y)(a\_x, a\_y)에 서 있고, 보물은 (b_x,b_y)(b\_x, b\_y)에 있다. 이 사막에는 오아시스도 있는데, 오아시스는 중심이 (p_x,p_y)(p\_x, p\_y)이고 반지름이 rr인 원으로 나타낼 수 있다.

성우의 체력은 이동한 유클리드 거리만큼 소모된다. 단, 오아시스 안에서는 성우의 체력이 소모되지 않는다. 성우가 보물의 위치에 도달하기 위해서 소모해야 하는 체력의 최솟값을 구해주자!

입력

정수 a_x,a_y,b_x,b_y,p_x,p_y,ra\_x, a\_y, b\_x, b\_y, p\_x, p\_y, r이 공백으로 구분되어 주어진다. (−106≤a_x,a_y,b_x,b_y,p_x,p_y≤106; 1≤r≤106)(-10^6 \leq a\_x, a\_y, b\_x, b\_y, p\_x, p\_y \leq 10^6; \ 1 \leq r \leq 10^6)

출력

성우가 보물의 위치에 도달하기 위해서 소모해야 하는 체력의 최솟값을 출력한다. 정답과의 절대오차 또는 상대오차가 10−910^{-9} 이하면 정답이다.

힌트

두 점 (x_1,y_1)(x\_1, y\_1)와 (x_2,y_2)(x\_2, y\_2) 사이의 유클리드 거리는 (x_1−x_2)2+(y_1−y_2)2\sqrt{(x\_1 - x\_2)^2 + (y\_1 - y\_2)^2}이다.

예제2

  1. 예제 1

    입력
    0 0 5 2 4 0 1
    
    예상 출력
    4.2360679775
    
  2. 예제 2

    입력
    0 0 5 2 -1 -1 1
    
    예상 출력
    5.385164807135