fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll                  long long
  3. #define endl                '\n'
  4. #define MOD                 1000000007
  5. #define sz                  200005
  6. using namespace std;
  7.  
  8. typedef long double T;
  9. const double eps = 1e-9;
  10. const double PI = acos((double) - 1.0);
  11. int sign(double x) { return (x > eps) - (x < -eps); }
  12.  
  13. struct PT {
  14.     double x, y;
  15.     PT() { x = 0, y = 0; }
  16.     PT(double x, double y) : x(x), y(y) {}
  17.     PT(const PT &p) : x(p.x), y(p.y)    {}
  18.     PT operator + (const PT &a) const { return PT(x + a.x, y + a.y); }
  19.     PT operator - (const PT &a) const { return PT(x - a.x, y - a.y); }
  20.     PT operator * (const double a) const { return PT(x * a, y * a); }
  21.     friend PT operator * (const double &a, const PT &b) { return PT(a * b.x, a * b.y); }
  22.     PT operator / (const double a) const { return PT(x / a, y / a); }
  23.     bool operator == (PT a) const { return sign(a.x - x) == 0 && sign(a.y - y) == 0; }
  24.     bool operator != (PT a) const { return !(*this == a); }
  25.     bool operator < (PT a) const { return sign(a.x - x) == 0 ? y < a.y : x < a.x; }
  26.     bool operator > (PT a) const { return sign(a.x - x) == 0 ? y > a.y : x > a.x; }
  27.     double norm() { return sqrt(x * x + y * y); }
  28.     double norm2() { return x * x + y * y; }
  29.     PT perp() { return PT(-y, x); }
  30.     double arg() { return atan2(y, x); }
  31.     PT truncate(double r) { // returns a vector with norm r and having same direction
  32.         double k = norm();
  33.         if (!sign(k)) return *this;
  34.         r /= k;
  35.         return PT(x * r, y * r);
  36.     }
  37. };
  38. template <typename T> int sgn(T x) {
  39.     return (T(0) < x) - (x < T(0));
  40. }
  41.  
  42. istream &operator >> (istream &in, PT &p) { return in >> p.x >> p.y; }
  43. ostream &operator << (ostream &out, PT &p) { return out << "(" << p.x << "," << p.y << ")"; }
  44. inline double dot(PT a, PT b) { return a.x * b.x + a.y * b.y; }
  45. inline double dist2(PT a, PT b) { return dot(a - b, a - b); }
  46. inline double dist(PT a, PT b) { return sqrt(dot(a - b, a - b)); }
  47. inline double cross(PT a, PT b) { return a.x * b.y - a.y * b.x; }
  48. inline double cross2(PT a, PT b, PT c) { return cross(b - a, c - a); }
  49.  
  50. // find a point from a through b with distance d
  51. PT point_along_line(PT a, PT b, double d) {
  52.     assert(a != b);
  53.     return a + (((b - a) / (b - a).norm()) * d);
  54. }
  55.  
  56. // minimum distance from point c to line through a and b
  57. double dist_from_point_to_line(PT a, PT b, PT c) {
  58.     return fabs(cross(b - a, c - a) / (b - a).norm());
  59. }
  60.  
  61.  
  62. void Solve()
  63. {
  64.     T x1, y1, x2, y2;
  65.     cin >> x1 >> y1 >> x2 >> y2;
  66.     PT TS(x1, y1);
  67.     PT TG(x2, y2);
  68.     cin >> x1 >> y1 >> x2 >> y2;
  69.     PT AS(x1, y1);
  70.     PT AG(x2, y2);
  71.  
  72.     T lo = 0.0, hi = max(dist(TS, TG), dist(AS, AG)), mid1, mid2, res = 1e9;
  73.     while (hi - lo > 0.0000001)
  74.     {
  75.         mid1 = lo + (hi - lo) / 3.0;
  76.         mid2 = hi - (hi - lo) / 3.0;
  77.         PT x = point_along_line(TS, TG, mid1);
  78.         PT y = point_along_line(AS, AG, mid1);
  79.         if (mid1 > dist(TS, TG))
  80.             x = TG;
  81.         if (mid1 > dist(AS, AG))
  82.             y = AG;
  83.         T c1 = dist(x, y);
  84.         x = point_along_line(TS, TG, mid2);
  85.         y = point_along_line(AS, AG, mid2);
  86.         if (mid2 > dist(TS, TG))
  87.             x = TG;
  88.         if (mid2 > dist(AS, AG))
  89.             y = AG;
  90.         T c2 = dist(x, y);
  91.  
  92.         if (c1 < c2 + eps)
  93.         {
  94.             res = c1;
  95.             hi = mid2;
  96.         }
  97.         else {
  98.             res = c2;
  99.             lo = mid1;
  100.         }
  101.     }
  102.     cout << fixed << setprecision(6) << res << endl;
  103. }
  104. int main()
  105. {
  106.     ios::sync_with_stdio(0);
  107.     cin.tie(0);
  108.     int t, T = 1;
  109.     cin >> T;
  110.     for (t = 1; t <= T; t++)
  111.         Solve();
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000.000000
https://ideone.com/auf8wW
language:
C++14 (gcc 8.3)
created:
127 days ago
visibility:
secret

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!