시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 22 13 12 60.000%

문제

Battle Royale games are the current trend in video games and Gamers Concealed Punching Circles (GCPC) is the most popular game of them all. The game takes place in an area that, for the sake of simplicity, can be thought of as a two-dimensional plane. Movement and positioning are a substantial part of the gameplay, but getting to a desired location can be dangerous. You are confident in your ability to handle the other players, however, while you are walking to your destination, there are two hazards posed by the game itself:

  • The game zone is bounded by a blue circle. Outside of this circle, there is a deadly force field that would instantly take you out of the game.
  • Inside the game zone, there is a red circle where you are exposed to artillery strikes. This circle is also too risky to enter.

You want to move from one spot on the map to another, but the direct path to your destination is blocked by the red circle, so you need to find a way around it. Can you find the shortest path that avoids all hazards by never leaving the blue or entering the red circle? Touching the boundaries of the circles is fine, as long as you do not cross them.

입력

The input consists of:

  • one line with two integers xc, yc specifying your current location;
  • one line with two integers xd, yd specifying your destination;
  • one line with three integers xb, yb, rb specifying the center and radius of the blue circle;
  • one line with three integers xr, yr, rr specifying the center and radius of the red circle.

All coordinates have an absolute value of at most 1 000, and 1 ≤ rb, rr ≤ 1 000. The red circle is strictly inside the blue circle. Your current location and destination are strictly inside the blue circle and strictly outside of the red circle, and the direct path between them is blocked by the red circle.

출력

Output the length of the shortest path that does not leave the blue or enter the red circle. The output must be accurate up to a relative or absolute error (whichever is lower) of 10−7.

예제 입력 1

0 0
10 0
0 0 1000
5 0 2

예제 출력 1

10.8112187742