fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ld = long double;
  4.  
  5. struct P {
  6.     ld x, y;
  7. };
  8.  
  9. inline P operator+(const P &a, const P &b){ return {a.x + b.x, a.y + b.y}; }
  10. inline P operator-(const P &a, const P &b){ return {a.x - b.x, a.y - b.y}; }
  11. inline P operator*(const P &a, const ld s){ return {a.x * s, a.y * s}; }
  12.  
  13. inline ld dot(const P &a, const P &b){ return a.x*b.x + a.y*b.y; }
  14. inline ld norm2(const P &a){ return dot(a,a); }
  15.  
  16. static ld min_sq_on_interval(ld tL, ld tR, const P &A1, const P &B1, const P &A2, const P &B2){
  17.     P C = A1 - A2;
  18.     P D = B1 - B2;
  19.     ld a = dot(D,D);
  20.     ld b = 2 * dot(C,D);
  21.     ld c = dot(C,C);
  22.     auto eval = [&](ld t)->ld{ return a*t*t + b*t + c; };
  23.     ld best = min(eval(tL), eval(tR));
  24.     const ld EPS = 1e-18L;
  25.     if (a > EPS){
  26.         ld t0 = -b / (2*a);
  27.         if (t0 > tL && t0 < tR) best = min(best, eval(t0));
  28.     }
  29.     return best;
  30. }
  31.  
  32. int main(){
  33.     ios::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.  
  36.     int T;
  37.     cin >> T;
  38.     cout.setf(ios::fixed);
  39.     cout << setprecision(10);
  40.  
  41.     while (T--){
  42.         long long TSx, TSy, TGx, TGy, ASx, ASy, AGx, AGy;
  43.         cin >> TSx >> TSy >> TGx >> TGy >> ASx >> ASy >> AGx >> AGy;
  44.         P S1 = {(ld)TSx, (ld)TSy}, G1 = {(ld)TGx, (ld)TGy};
  45.         P S2 = {(ld)ASx, (ld)ASy}, G2 = {(ld)AGx, (ld)AGy};
  46.         P diff1 = G1 - S1, diff2 = G2 - S2;
  47.         ld d1 = sqrtl(norm2(diff1)), d2 = sqrtl(norm2(diff2));
  48.         P v1 = {diff1.x / d1, diff1.y / d1};
  49.         P v2 = {diff2.x / d2, diff2.y / d2};
  50.         ld tmin = min(d1, d2), tmax = max(d1, d2);
  51.         ld best_sq = min_sq_on_interval(0.0L, tmin, S1, v1, S2, v2);
  52.         if (tmax - tmin > 1e-18L){
  53.             if (d1 < d2) best_sq = min(best_sq, min_sq_on_interval(tmin, tmax, G1, P{0,0}, S2, v2));
  54.             else best_sq = min(best_sq, min_sq_on_interval(tmin, tmax, S1, v1, G2, P{0,0}));
  55.         }
  56.         best_sq = min(best_sq, norm2(G1 - G2));
  57.         cout << (double)sqrt((long double)best_sq) << '\n';
  58.     }
  59. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
4
0 0 -2 2
-1 -1 4 4
4 0 2 0
6 0 8 0
1 0 1 1
-1 0 1 1
-8 9 2 6
-10 -10 17 20
stdout
copy 
1.0000000000
2.0000000000
0.0000000000
1.7839059510
https://ideone.com/UC1pEk
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!