HUST Monthly 2010.04.05

From: 2010-04-05 12:00:00 To: 2010-04-05 17:00:00 Now: 2017-09-20 01:03:18 Status: Public

F - Push Over

Time Limit: 1s Memory Limit: 128MB

Submissions: 14 Solved: 1
Description
LL and ErBao were back!!!...along with them was HH. HH was angry about being tricked last time, so he decided to push them over this time. On this beautiful Sunday, LL and ErBao were playing “Duo Mao Mao” and HH saw his chances come. At this time, LL was counting numbers blindfolded at point A, and ErBao stood at point B a distance from LL. HH is standing at point S. Now HH wanted to push them over one by one (in any order), and escape to point T immediately. There are no obstacles. Here comes the problem. Since it had just snowed, the ground was very slippery. Since HH wanted to do it quickly, the radius of curvature on any point of his path couldn’t be too small, in particular, not smaller than R. In order to surprise them suddenly, HH decided to push them over from their back side, which means HH must face the same direction with the push-over object when he passed through the pushing point. Please help HH plan a path satisfying the above restriction with the minimum total length. For simplicity, you should only calculate the length of this path.
Input
The input contains multiple cases separated by a blank line terminated with EOF. For each case, first line contains one integer: R. Then four lines describes coordinates of S, A, B, and T. XS, YS XA, YA, DXA, DYA XB, YB, DXB, DYB XT, YT DX and DY stands for the direction LL and ErBao faced to. All the values are integers and the absolute value of them will not exceed 100. It is guaranteed that the distance between any two of S, A, B, and T is larger than 0. You can assume the push action do not affect the movement of HH.
Output
For each case output the length of the shortest path for HH, accurate to two decimal places.
Sample Input
1
0 0
1 0 1 0
2 0 1 0
3 0

1
0 0
1 0 -1 0
2 0 -1 0
3 0

1
0 0
1 0 1 0
1 3 -1 0
0 3

1
0 0
1 1 0 1
0 2 -1 0
-1 1
Sample Output
3.00
13.14
6.14
4.71
Hint
                                      Sample #1



                  Sample #2



                  Sample #3



                  Sample #4



Source
Hust Monthly 10.04.05/Isun