IX Samara Regional Intercollegiate Programming Contest F 三分

F. Two Points

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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两个方向的速度 问运动过程中两个点间的最小距离

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

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<cmath>

 using namespace std;

 double x1,x2,y1,y2;

 double vx1,vx2,vy1,vy2;

 double f(double t)

 {

     double xx1,xx2,yy1,yy2;

     xx1=x1+t*vx1;

     xx2=x2+t*vx2;

     yy1=y1+t*vy1;

     yy2=y2+t*vy2;

     return sqrt((xx1-xx2)*(xx1-xx2)+(yy1-yy2)*(yy1-yy2));

 }

 int main()

 {

     scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

     scanf("%lf %lf %lf %lf",&vx1,&vy1,&vx2,&vy2);

     double l=,r=1e9,m1,m2;

    for(int i=;i<;i++)

     {

        m1=l+(r-l)/;

        m2=r-(r-l)/;

        if(f(m1)<f(m2))

             r=m2;

        else

         l=m1;

     }

     printf("%f\n",f(l));

     return ;

 }

巴特西

IX Samara Regional Intercollegiate Programming Contest F 三分

最新文章

热门文章