fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define double long double
  6. void fileIO()
  7. {
  8.     ios_base::sync_with_stdio(0);
  9.     cin.tie(0);
  10.     cout.tie(0);
  11.     freopen("raydist.in", "r", stdin);
  12.     freopen("raydist.out", "w", stdout);
  13. #ifndef ONLINE_JUDGE
  14.     freopen("input.txt", "r", stdin);
  15.     freopen("output.txt", "w", stdout);
  16. #endif
  17. }
  18.  
  19. typedef double T;
  20. typedef complex<T> pt;
  21. #define x real()
  22. #define y imag()
  23. #define vec(a, b) (pt)(b - a)
  24. #define M_PI 3.14159265358979323846
  25. #define eps 1e-9
  26. #define dot(a, b) ((conj(a) * (b)).real())
  27. #define cross(a, b) ((conj(a) * (b)).imag())
  28. #define perp(p) \
  29.     (pt) { -p.y, p.x } // the rotation by 90◦
  30. #define sq(a) a.x *a.x + a.y *a.y
  31. #define orient(a, b, c) cross(b - a, c - a)
  32. struct Line
  33. {
  34.     pt v;
  35.     T c;
  36.  
  37.     // from vector and offset
  38.     Line(pt v, T c) : v(v), c(c) {}
  39.     // ax + by = c
  40.     Line(T a, T b, T c) : v({-b, a}), c(c) {}
  41.     // from two points
  42.     Line(pt a, pt b) : v(b - a), c(cross(v, a)) {}
  43.     // left if positive, right if negative, on the line otherwise
  44.     T side(pt p) { return cross(v, p) - c; }
  45.     // distance from p to the line
  46.     double dist(pt p) { return abs(side(p)) / abs(v); }
  47.     double sqDist(pt p) { return side(p) * side(p) / (double)sq(v); }
  48.     Line perpThrough(pt p) { return {p, p + perp(v)}; }
  49.     // sort points on line
  50.     bool cmpProj(pt p, pt q) { return dot(v, p) < dot(v, q); }
  51.     // translate a line by direction vector t, only c changes
  52.     Line translate(pt t) { return {v, c + cross(v, t)}; }
  53.     // shift the line left by distance dist, direction vector t is (dist / abs(v)) * perp(v)
  54.     Line shiftLeft(double dist) { return {v, c + dist * abs(v)}; }
  55.     // intersection point between two lines
  56.     bool inter(Line l, pt &out)
  57.     {
  58.         T d = cross(v, l.v);
  59.         if (d == 0)
  60.             return false;
  61.         out = (l.v * c - v * l.c) / d; // requires floating-point coordinates
  62.         return true;
  63.     }
  64.     // projection of a point P on a line l is the point on l that is closest to P.
  65.     pt proj(pt p) { return p - perp(v) * side(p) / sq(v); }
  66.     // The reflection of point P by line l is the point on the other side of l that is at the same distance and has the same orthogonal projection.
  67.     pt refl(pt p) { return p - perp(v) * (2.0 * side(p) / sq(v)); }
  68.  
  69.     /*
  70.         l_ext(l1,l2)▲
  71.                    │
  72.                    │
  73.                    │               l2
  74.      xx            │        xxxxxxxx
  75.       xxxx         │        xxxxxxx
  76.           xxx      │        xxxxxx
  77.             xxx    │     xxx   x
  78.               xx   │   xxx
  79.                xxx │ xxx                 l_int(l1,l2)
  80. ─────────────────xxxxx─────────────────►
  81.                xxxxxxxxx
  82.              xxx   │    xx
  83.            xxx     │      xxx
  84.          xxx       │        xxxx   xx
  85.                    │           xxxxxxx
  86.                    │            xxxxxxx
  87.                    │          xxxxxxxxxx
  88.                    │          xxxxxxxxxxx
  89.  
  90.                                  l1
  91.     */
  92.  
  93.     Line bisector(Line l, bool interior)
  94.     {
  95.         assert(cross(v, l.v) != 0); // l1 and l2 cannot be parallel!
  96.         double sign = interior ? 1 : -1;
  97.         return {l.v / abs(l.v) + v / abs(v) * sign,
  98.                 l.c / abs(l.v) + c / abs(v) * sign};
  99.     }
  100. };
  101.  
  102. // checks if a point lies on disk formed by diameter [a,b]
  103. static bool inDisk(pt a, pt b, pt p) { return dot(a - p, b - p) <= 0; }
  104. // check if point is on the segment [a,b]
  105. static bool onSegment(pt a, pt b, pt p) { return orient(a, b, p) == 0 && inDisk(a, b, p); }
  106.  
  107. // one point intersection of two segments
  108. bool properInter(pt a, pt b, pt c, pt d, pt &out)
  109. {
  110.     double oa = orient(c, d, a),
  111.            ob = orient(c, d, b),
  112.            oc = orient(a, b, c),
  113.            od = orient(a, b, d);
  114.     // Proper intersection exists if opposite signs
  115.     if (oa * ob < 0 && oc * od < 0)
  116.     {
  117.         out = (a * ob - b * oa) / (ob - oa);
  118.         return true;
  119.     }
  120.     return false;
  121. }
  122.  
  123. // comparable to create set of points
  124. struct cmpX
  125. {
  126.     bool operator()(pt a, pt b) const
  127.     {
  128.         return make_pair(a.x, a.y) < make_pair(b.x, b.y);
  129.     }
  130. };
  131.  
  132. // the intersection between two points
  133. set<pt, cmpX> intersections(pt a, pt b, pt c, pt d)
  134. {
  135.     pt out;
  136.     if (properInter(a, b, c, d, out))
  137.         return {out}; // only one intersection
  138.     set<pt, cmpX> s;
  139.     if (onSegment(c, d, a))
  140.         s.insert(a);
  141.     if (onSegment(c, d, b))
  142.         s.insert(b);
  143.     if (onSegment(a, b, c))
  144.         s.insert(c);
  145.     if (onSegment(a, b, d))
  146.         s.insert(d);
  147.     return s;
  148. }
  149.  
  150. double segmentPointDistance(pt a, pt b, pt p)
  151. {
  152.     if (a != b)
  153.     {
  154.         Line l(a, b);
  155.         if (l.cmpProj(a, p) && l.cmpProj(p, b)) // if closest to projection
  156.             return l.dist(p);                   // output distance to Line
  157.     }
  158.     return min(abs(p - a), abs(p - b)); // otherwise distance to A or B
  159. }
  160.  
  161. double segmentSegmentDistance(pt a, pt b, pt c, pt d)
  162. {
  163.     pt dummy;
  164.     if (properInter(a, b, c, d, dummy))
  165.         return 0;
  166.     return min({segmentPointDistance(a, b, c), segmentPointDistance(a, b, d),
  167.                 segmentPointDistance(c, d, a), segmentPointDistance(c, d, b)});
  168. }
  169. double rayPointDistance(pt a, pt b, pt p)
  170. {
  171.     if (a != b)
  172.     {
  173.         Line l(a, b);
  174.         if (l.cmpProj(a, p))  // if closest to projection
  175.             return l.dist(p); // output distance to Line
  176.     }
  177.     return abs(p - a); // otherwise distance to A
  178. }
  179.  
  180. bool intersectSegments(pt a, pt b, pt c, pt d, pt &intersect)
  181. {
  182.     double d1 = cross(vec(b, a), vec(c, d)), d2 = cross(vec(c, a), vec(c, d)), d3 = cross(vec(b, a), vec(c, a));
  183.  
  184.     if (fabs(d1) < eps)
  185.         return false; /// parllel or identical
  186.  
  187.     double t1 = d2 / d1, t2 = d3 / d1;
  188.     intersect = a + (b - a) * t1;
  189.  
  190.     /// segment: [0, 1]
  191.     /// ray: [0, INF]
  192.     /// line: [-INF, INF]
  193.  
  194.     /// make sure that eps is not too accurate
  195.     if (t1 < -eps or t2 < -eps)
  196.         return false;
  197.  
  198.     return true;
  199. }
  200.  
  201. double rayRayDistance(pt a, pt b, pt c, pt d)
  202. {
  203.     pt dummy;
  204.     if (intersectSegments(a, b, c, d, dummy))
  205.         return 0;
  206.     return min(rayPointDistance(a, b, c), rayPointDistance(c, d, a));
  207. }
  208.  
  209. void Striker()
  210. {
  211.     int a, b;
  212.     cin >> a >> b;
  213.     pt p1(a, b);
  214.     cin >> a >> b;
  215.     pt p2(a, b);
  216.     cin >> a >> b;
  217.     pt p3(a, b);
  218.     cin >> a >> b;
  219.     pt p4(a, b);
  220.     cout << fixed << setprecision(12) << rayRayDistance(p1, p2, p3, p4);
  221. }
  222.  
  223. signed main()
  224. {
  225.     fileIO();
  226.     int _t = 1;
  227.     // cin >> _t;
  228.     for (int i = 0; i < _t; ++i)
  229.     {
  230.         Striker();
  231.     }
  232. }
  233.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u2MMk0
language:
C++ (gcc 8.3)
created:
12 hours 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!