IX Samara Regional Intercollegiate Programming Contest F 三分

There are two points (x₁, y₁) and (x₂, y₂) on the plane. They move with the velocities (v_x₁, v_y₁) and (v_x₂, v_y₂). Find the minimal distance between them ever in future.

Input

The first line contains four space-separated integers x₁, y₁, x₂, y₂ ( - 10⁴ ≤ x₁, y₁, x₂, y₂ ≤ 10⁴) — the coordinates of the points.

The second line contains four space-separated integers v_x₁, v_y₁, v_x₂, v_y₂ ( - 10⁴ ≤ v_x₁, v_y₁, v_x₂, v_y₂ ≤ 10⁴) — the velocities of the points.

Output

Output a real number d — the minimal distance between the points. Absolute or relative error of the answer should be less than 10^- 6.

Examples

Input

1 1 2 2
0 0 -1 0

Output

1.000000000000000

Input

1 1 2 2
0 0 1 0

Output

1.414213562373095

题意：给你两个点 以及这两个点的x，y两个方向的速度 问运动过程中两个点间的最小距离

题解：第一次三分处理 类比二分 二分是针对单调函数的数值确定
     三分不仅适用于单调函数，而且适用于凸函数
     运动的两点间的距离的图像是不确定的  三分处理..

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<stack>
 7 #include<cmath>
 8 using namespace std;
 9 double x1,x2,y1,y2;
10 double vx1,vx2,vy1,vy2;
11 double f(double t)
12 {
13     double xx1,xx2,yy1,yy2;
14     xx1=x1+t*vx1;
15     xx2=x2+t*vx2;
16     yy1=y1+t*vy1;
17     yy2=y2+t*vy2;
18     return sqrt((xx1-xx2)*(xx1-xx2)+(yy1-yy2)*(yy1-yy2));
19 }
20 int main()
21 {
22     scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
23     scanf("%lf %lf %lf %lf",&vx1,&vy1,&vx2,&vy2);
24     double l=0,r=1e9,m1,m2;
25    for(int i=0;i<200;i++)
26     {
27        m1=l+(r-l)/3;
28        m2=r-(r-l)/3;
29        if(f(m1)<f(m2))
30             r=m2;
31        else
32         l=m1;
33     }
34     printf("%f
",f(l));
35     return 0;
36 }