fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ld = long double;
  4.  
  5. struct P { ld x, y; };
  6.  
  7. inline P operator+(const P &a, const P &b){ return {a.x + b.x, a.y + b.y}; }
  8. inline P operator-(const P &a, const P &b){ return {a.x - b.x, a.y - b.y}; }
  9. inline P operator*(const P &a, const ld s){ return {a.x * s, a.y * s}; }
  10. inline P operator/(const P &a, const ld s){ return {a.x / s, a.y / s}; }
  11.  
  12. inline ld dot(const P &a, const P &b){ return a.x*b.x + a.y*b.y; }
  13. inline ld norm2(const P &a){ return dot(a,a); }
  14. ld distance2(const P &a, const P &b){ return norm2(a-b); }
  15.  
  16. ld min_distance(ld tL, ld tR, const P &A1, const P &v1, const P &A2, const P &v2){
  17.     P C = A1 - A2;
  18.     P D = v1 - v2;
  19.     ld a = dot(D,D);
  20.     ld b = 2*dot(C,D);
  21.     ld c = dot(C,C);
  22.     ld res = min({c, a*tL*tL + b*tL + c, a*tR*tR + b*tR + c});
  23.     if(a > 1e-15L){
  24.         ld t0 = -b/(2*a);
  25.         if(t0 >= tL && t0 <= tR) res = min(res, a*t0*t0 + b*t0 + c);
  26.     }
  27.     return res;
  28. }
  29.  
  30. int main(){
  31.     ios::sync_with_stdio(false);
  32.     cin.tie(nullptr);
  33.     cout << fixed << setprecision(10);
  34.  
  35.     int T; cin >> T;
  36.     while(T--){
  37.         long long TSx, TSy, TGx, TGy, ASx, ASy, AGx, AGy;
  38.         cin >> TSx >> TSy >> TGx >> TGy >> ASx >> ASy >> AGx >> AGy;
  39.  
  40.         P S1 = {(ld)TSx, (ld)TSy}, G1 = {(ld)TGx, (ld)TGy};
  41.         P S2 = {(ld)ASx, (ld)ASy}, G2 = {(ld)AGx, (ld)AGy};
  42.  
  43.         P diff1 = G1 - S1, diff2 = G2 - S2;
  44.         ld d1 = sqrtl(norm2(diff1)), d2 = sqrtl(norm2(diff2));
  45.  
  46.         P v1 = (d1 < 1e-15L) ? P{0,0} : diff1 / d1;
  47.         P v2 = (d2 < 1e-15L) ? P{0,0} : diff2 / d2;
  48.  
  49.         ld tmin = min(d1,d2), tmax = max(d1,d2);
  50.  
  51.         ld ans = min_distance(0.0L, tmin, S1, v1, S2, v2);
  52.  
  53.         if(tmax - tmin > 1e-15L){
  54.             if(d1 < d2) ans = min(ans, min_distance(tmin, tmax, G1, P{0,0}, S2, v2));
  55.             else ans = min(ans, min_distance(tmin, tmax, S1, v1, G2, P{0,0}));
  56.         }
  57.  
  58.         ans = min(ans, distance2(G1, G2));
  59.  
  60.         cout << sqrtl(ans) << '\n';
  61.     }
  62. }
Success #stdin #stdout 0s 5320KB
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/eUFPVn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 day 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!