Submission #69887760

---

Source Code Expand

// Problem: 'E - Closest Moment'
// Contest: 'AtCoder - AtCoder Beginner Contest 426'
// URL: 'https://atcoder.jp/contests/abc426/tasks/abc426_e'
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by competitive-companion.el (https://github.com/luishgh/competitive-companion.el)

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

typedef long double ld;
const ld eps = 1e-9;

#define sq(x) ((x)*(x))

bool eq(ld a, ld b) {
  return abs(a - b) <= eps;
}

struct pt {
  ld x, y;
  pt(ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}

  pt operator + (const pt p) const  {return pt(x+p.x, y+p.y); }
  pt operator - (const pt p) const  {return pt(x-p.x, y-p.y); }
  pt operator * (const ld c) const  {return pt(x*c, y*c); }
  pt operator / (const ld c) const { return pt(x/c  , y/c  ); }
};

ld dist(pt p, pt q) {
  return hypot(p.y - q.y, p.x - q.x);
}

ld dist2(pt p, pt q) {
  return sq(p.x - q.x) + sq(p.y - q.y);
}


ld norm(pt v) { // norma do vetor
	return dist(pt(0, 0), v);
}

pt get_comb(pt a, pt b, ld t) {
  ld n = norm(b - a);
  if (t >= n) return b;
  pt v = (b - a) / n;
  return v * t + a;
}

ld get_dist(pt ta, pt tb, pt aa, pt ab, ld t) {
  pt tt = get_comb(ta, tb, t);
  pt at = get_comb(aa, ab, t);
  // cerr << t << " {" << tt.x << ", " << tt.y << "} {" << at.x << ", " << at.y << "}" << endl;

  return dist(tt, at);
} 

ld get_dist2(pt ta, pt tb, pt aa, pt ab, ld t) {
  pt tt = get_comb(ta, tb, t);
  pt at = get_comb(aa, ab, t);
  // cerr << t << " {" << tt.x << ", " << tt.y << "} {" << at.x << ", " << at.y << "}" << endl;

  return dist2(tt, at);
} 

void solve() {
  ll tsx, tsy, tgx, tgy;
  cin >>  tsx >>  tsy >>  tgx >>  tgy;
  ll asx, asy, agx, agy;
  cin >>  asx >>  asy >>  agx >>  agy;
  pt ta(tsx, tsy);
  pt tb(tgx, tgy);

  pt aa(asx, asy);
  pt ab(agx, agy);

  if (norm(tb - ta) < norm(ab - aa)) {
    swap(ta, aa);
    swap(tb, ab);
  }

  // ld l = get_dist2(ta, tb, aa, ab, 0);
  ld la = 0;

  ld ra = norm(ab - aa); 
  // ld r = get_dist2(ta, tb, aa, ab, ra);

  while (ra - la > eps) {
    // cerr << la << ' ' << ra << endl;
    ld m1 = la + (ra - la) / 3;
    ld m2 = ra - (ra - la) / 3;
    ld f1 = get_dist2(ta, tb, aa, ab, m1);
    ld f2 = get_dist2(ta, tb, aa, ab, m2);
    if (f1 > f2)
      la = m1;
    else
      ra = m2;
  }

  ld ans = get_dist(ta, tb, aa, ab, la);

  la = norm(ab - aa), ra = norm(tb - ta);

  while (ra - la > eps) {
    // cerr << la << ' ' << ra << endl;
    ld m1 = la + (ra - la) / 3;
    ld m2 = ra - (ra - la) / 3;
    ld f1 = get_dist2(ta, tb, aa, ab, m1);
    ld f2 = get_dist2(ta, tb, aa, ab, m2);
    if (f1 > f2)
      la = m1;
    else
      ra = m2;
  }

  ans = min(ans, get_dist(ta, tb, aa, ab, la));

  // cerr << la << endl;
  cout << ans << endl;
}

int main() {_;

  cout << fixed << setprecision(15);
  int ttt; cin >> ttt;
  while (ttt--) solve();

  return 0;
}

Submission Info

Judge Result