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. // 두 선형 운동의 거리 제곱 최소값 구하기
  17. static ld min_sq_on_interval(ld tL, ld tR, const P &A1, const P &B1, const P &A2, const P &B2){
  18.     P C = A1 - A2;
  19.     P D = B1 - B2;
  20.     ld a = dot(D,D);
  21.     ld b = 2 * dot(C,D);
  22.     ld c = dot(C,C);
  23.  
  24.     auto eval = [&](ld t)->ld{ return a*t*t + b*t + c; };
  25.     ld best = min(eval(tL), eval(tR));
  26.  
  27.     const ld EPS = 1e-18L;
  28.     if (a > EPS){
  29.         ld t0 = -b / (2*a);
  30.         if (t0 > tL && t0 < tR){
  31.             best = min(best, eval(t0));
  32.         }
  33.     }
  34.     return best;
  35. }
  36.  
  37. int main(){
  38.     ios::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.  
  41.     int T;
  42.     cin >> T;
  43.     cout.setf(std::ios::fixed);
  44.     cout << setprecision(10);
  45.  
  46.     while (T--){
  47.         long long TSx, TSy, TGx, TGy, ASx, ASy, AGx, AGy;
  48.         cin >> TSx >> TSy >> TGx >> TGy >> ASx >> ASy >> AGx >> AGy;
  49.  
  50.         P S1 = {(ld)TSx, (ld)TSy};
  51.         P G1 = {(ld)TGx, (ld)TGy};
  52.         P S2 = {(ld)ASx, (ld)ASy};
  53.         P G2 = {(ld)AGx, (ld)AGy};
  54.  
  55.         P diff1 = G1 - S1;
  56.         P diff2 = G2 - S2;
  57.  
  58.         ld d1 = sqrtl(max((ld)0.0L, norm2(diff1)));
  59.         ld d2 = sqrtl(max((ld)0.0L, norm2(diff2)));
  60.  
  61.         // 속도 벡터 (단위 벡터)
  62.         P v1 = {diff1.x / d1, diff1.y / d1};
  63.         P v2 = {diff2.x / d2, diff2.y / d2};
  64.  
  65.         ld tmin = min(d1, d2);
  66.         ld tmax = max(d1, d2);
  67.  
  68.         // 1) 둘 다 이동 중
  69.         ld best_sq = min_sq_on_interval(0.0L, tmin, S1, v1, S2, v2);
  70.  
  71.         // 2) 한쪽이 정지한 구간
  72.         if (tmax - tmin > 1e-18L){
  73.             if (d1 < d2){
  74.                 // 타카하시 정지, 아오키 이동
  75.                 best_sq = min(best_sq, min_sq_on_interval(tmin, tmax, G1, P{0,0}, S2, v2));
  76.             } else {
  77.                 // 아오키 정지, 타카하시 이동
  78.                 best_sq = min(best_sq, min_sq_on_interval(tmin, tmax, S1, v1, G2, P{0,0}));
  79.             }
  80.         }
  81.  
  82.         // 3) 둘 다 정지 후
  83.         best_sq = min(best_sq, norm2(G1 - G2));
  84.  
  85.         cout << (double)sqrt((long double)best_sq) << '\n';
  86.     }
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5288KB
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/CvClex
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!