ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Personal Contest 2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Thread in a Hyperspace

Time limit: 1.0 second
Memory limit: 64 MB
There are two starcrafts and a drop of water (nobody knows where it comes from) in a hyperspace (it’s well-known that hyperspace has 8 dimensions). Whereas there’re anisotropic distortions because of the hyperspace transfer you may assume the ships as points (A and B) and the drop as a sphere with radius R and center in the point C. Coordinates of all the points are integer and their absolute values don’t exceed 1000. The drop is motionless. The radius R is a positive integer not exceeding 3000. The distance from the point C to the points A and B is greater than R.
The starcraft B is distressed (and motionless as well), and the starcraft A hurries to succor. You are to find out the length of the short cut from the point A to the point B not crossing the sphere (the starcraft may move along the edge of the sphere).

Input

There are three lines in succession containing coordinates of the points A, B and C respectively. Each of the lines consists of 8 integers. The fourth line contains positive integer R, that is the sphere radius.

Output

Should contain the length of the short cut within 2 digits after a decimal point. There must be exactly 2 digits after a decimal point. The result is to be rounded according to the standard mathematical rules.

Sample

inputoutput
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
10 10 10 10 5 5 5 5
3
1.00
Problem Author: Alexander Mironenko and Alexey Lakhtin
Problem Source: USU Personal Contest 2004
To submit the solution for this problem go to the Problem set: 1285. Thread in a Hyperspace