Closest Distance LOJ 1146

#include<bits/stdc++.h>
using namespace std;

const double eps = 1e-10;

struct point{
  long double x, y;
};

long double distance(point a, point b) {
  long double retsq = abs(a.x-b.x)*abs(a.x-b.x) + abs(a.y-b.y)*abs(a.y-b.y);
  long double ret = sqrtl(retsq);
  return ret;
}

point move(point A, point B, long double len) {
  point ret;
  long double AB = distance(A, B);

  //ratios
  long double m1 = len/AB;
  long double m2 = 1-m1;

  ret.x = (A.x*m2+B.x*m1)/(m1+m2);
  ret.y = (A.y*m2+B.y*m1)/(m1+m2);
  return ret;
}

void PlayGround() {
  point A, B, C, D;
  cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;

  //lengths
  long double AB = distance(A, B);
  long double CD = distance(C, D);

  //assuming the total time taken is 1 second
  long double v1 = AB, v2 = CD; //velocities


  long double ans = LLONG_MAX;
  long double l = 0, r = 1;
  while(r-l>eps) {
    long double m1 = l+(r-l)/3;
    long double m2 = r-(r-l)/3;

    point _A1 = move(A, B, m1*v1);
    point _C1 = move(C, D, m1*v2);

    point _A2 = move(A, B, m2*v1);
    point _C2 = move(C, D, m2*v2);

    long double d1 = distance(_A1, _C1);
    long double d2 = distance(_A2, _C2);

    if(d1<d2) {
      ans = d1;
      r = m2;
    } else {
      ans = d2;
      l = m1;
    }
  }

  cout<<setprecision(6)<<fixed<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cerr<<setprecision(15)<<fixed;

  int T;
  cin >> T;
  for(int i=1; i<=T; ++i) {
    cout << "Case " << i << ": ";
    PlayGround();
  }
  return 0;
}