Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long double ld;
  6. typedef long long ll;
  7.  
  8. const ld EPS = 1e-9;
  9.  
  10. struct Point
  11. {
  12.     ld x, y;
  13.     Point operator + (const Point& B)
  14.     {
  15.         return {B.x + x, B.y + y};
  16.     }
  17.     Point operator - (const Point& B)
  18.     {
  19.         return {B.x - x, B.y - y};
  20.     }
  21.     ld operator ^ (const Point& B)
  22.     {
  23.         return x * B.y - y * B.x;
  24.     }
  25.     ld operator * (const Point& B)
  26.     {
  27.         return x * B.x + y * B.y;
  28.     }
  29. };
  30.  
  31. struct Line
  32. {
  33.     ld a, b, c;
  34. };
  35.  
  36. Point makePoint(ll x, ll y)
  37. {
  38.     Point p;
  39.     p.x = x;
  40.     p.y = y;
  41.     return p;
  42. }
  43.  
  44. Line makeLine(ld a, ld b, ld c)
  45. {
  46.     Line l;
  47.     l.a = a;
  48.     l.b = b;
  49.     l.c = c;
  50.     return l;
  51. }
  52.  
  53. Line makeLine(Point p1, Point p2)
  54. {
  55.     Line l;
  56.     l.a = p1.y - p2.y;
  57.     l.b = p2.x - p1.x;
  58.     l.c = p1.x * p2.y - p2.x * p1.y;
  59.     return l;
  60. }
  61.  
  62. Point readPoint()
  63. {
  64.     Point p;
  65.     cin >> p.x >> p.y;
  66.     return p;
  67. }
  68.  
  69. ld length(Point p)
  70. {
  71.     return sqrt(p.x * p.x + p.y * p.y);
  72. }
  73.  
  74. ld Distance(Point p, Point A, Point B)
  75. {
  76.     Line l = makeLine(A, B);
  77.     return (abs)(l.a * p.x + l.b * p.y + l.c) / sqrt(l.a * l.a + l.b * l.b);
  78. }
  79.  
  80. bool checkParallel(Line l1, Line l2)
  81. {
  82.     return abs(l1.a * l2.b - l2.a * l1.b) < EPS;
  83. }
  84.  
  85. Point LineIntersec(Line l1, Line l2)
  86. {
  87.     Point p;
  88.     p.x = -(l1.c * l2.b - l2.c * l1.b) / (l1.a * l2.b - l2.a * l1.b);
  89.     p.y = -(l1.a * l2.c - l2.a * l1.c) / (l1.a * l2.b - l2.a * l1.b);
  90.     return p;
  91. }
  92.  
  93. bool PointonSegment(Point p1, Point p2, Point p)
  94. {
  95.     Line l = makeLine(p1, p2);
  96.     if (abs(l.a * p.x + l.b * p.y + l.c) > EPS)
  97.         return false;
  98.     return p.x - max(p1.x, p2.x) < EPS && p.x - min(p1.x, p2.x) > -EPS &&
  99.          p.y - max(p1.y, p2.y) < EPS && p.y - min(p1.y, p2.y) > -EPS;
  100. }
  101.  
  102. bool PointonRay(Point C, Point D, Point A)
  103. {
  104.     if (abs(A.x - C.x) + abs(A.y - C.y) < EPS)
  105.         return true;
  106.     Line l = makeLine(C, D);
  107.     if (abs(l.a * A.x + l.b * A.y + l.c) > EPS)
  108.         return false;
  109.     if (abs(C.x + C.y - D.x - D.y) < EPS)
  110.         return ((C.x - D.x) * (C.x - A.x) > 0);
  111.     if (D.x + D.y > C.x + C.y)
  112.         return (A.x + A.y >= C.x + C.y);
  113.     return (A.x + A.y <= C.x + C.y);
  114. }
  115.  
  116. bool RaySegmentIntersec(Point C, Point D, Point A, Point B)
  117. {
  118.     Line l1 = makeLine(A, B);
  119.     Line l2 = makeLine(C, D);
  120.     if (checkParallel(l1, l2))
  121.     {
  122.         if (abs(l1.a * l2.c - l2.a * l1.c) > EPS)
  123.             return false;
  124.         return (PointonRay(C, D, A) || PointonRay(C, D, B));
  125.     }
  126.     Point p = LineIntersec(l1, l2);
  127.     return (PointonSegment(A, B, p) && PointonRay(C, D, p));
  128. }
  129.  
  130. bool SegmentIntersec(Point A, Point B, Point C, Point D)
  131. {
  132.     return RaySegmentIntersec(A, B, C, D) && RaySegmentIntersec(B, A, C, D);
  133. }
  134.  
  135. bool RaysIntersec(Point A, Point B, Point C, Point D)
  136. {
  137.     Line l1 = makeLine(A, B);
  138.     Line l2 = makeLine(C, D);
  139.     if (checkParallel(l1, l2))
  140.     {
  141.         if (abs(l1.a * l2.c - l2.a * l1.c) > EPS)
  142.             return false;
  143.         return (PointonRay(A, B, C) || PointonRay(C, D, A));
  144.     }
  145.     Point p = LineIntersec(l1, l2);
  146.     return (PointonRay(A, B, p) && PointonRay(C, D, p));
  147. }
  148.  
  149. bool RayLineIntersec(Point A, Point B, Point C, Point D)
  150. {
  151.     return RaysIntersec(A, B, C, D) || RaysIntersec(A, B, D, C);
  152. }
  153.  
  154. ld DistanceRayPoint(Point A, Point B, Point C)
  155. {
  156.     if (((B - A) ^ (C - A)) < 0)
  157.         return length(A - C);
  158.     return Distance(C, A, B);
  159. }
  160.  
  161. ld DistanceSegmentPoint(Point A, Point B, Point C)
  162. {
  163.     return max(DistanceRayPoint(A, B, C), DistanceRayPoint(B, A, C));
  164. }
  165.  
  166. ld DistanceSegments(Point A, Point B, Point C, Point D)
  167. {
  168.     if (SegmentIntersec(A, B, C, D))
  169.         return 0;
  170.     return min(min(DistanceSegmentPoint(A, B, C), DistanceSegmentPoint(A, B, D)),
  171.                min(DistanceSegmentPoint(C, D, A), DistanceSegmentPoint(C, D, B)));
  172. }
  173.  
  174. ld DistanceRays(Point A, Point B, Point C, Point D)
  175. {
  176.     if (RaysIntersec(A, B, C, D))
  177.         return 0;
  178.     return min(DistanceRayPoint(C, D, A), DistanceRayPoint(A, B, C));
  179. }
  180.  
  181. ld DistanceRaySegment(Point C, Point D, Point A, Point B)
  182. {
  183.     return max(DistanceRays(C, D, A, B), DistanceRays(C, D, B, A));
  184. }
  185.  
  186. ld DistanceRayLine(Point A, Point B, Point C, Point D)
  187. {
  188.     if (RayLineIntersec(A, B, C, D))
  189.         return 0;
  190.     return Distance(A, C, D);
  191. }
  192.  
  193. ld DistanceLineSegment(Point C, Point D, Point A, Point B)
  194. {
  195.     if (RaySegmentIntersec(C, D, A, B) || RaySegmentIntersec(D, C, A, B))
  196.         return 0;
  197.     return min(Distance(A, C, D), Distance(B, C, D));
  198. }
  199.  
  200. int main()
  201. {
  202.     freopen("hard-geometry.in", "r", stdin);
  203.     freopen("hard-geometry.out", "w", stdout);
  204.     cout.precision(20);
  205.     Point A = readPoint(), B = readPoint(), C = readPoint(), D = readPoint();
  206.     cout << length(C - A) << endl;
  207.     cout << DistanceSegmentPoint(C, D, A) << endl;
  208.     cout << DistanceRayPoint(C, D, A) << endl;
  209.     cout << Distance(A, C, D) << endl;
  210.     cout << DistanceSegmentPoint(A, B, C) << endl;
  211.     cout << DistanceSegments(A, B, C, D) << endl;
  212.     cout << DistanceRaySegment(C, D, A, B) << endl;
  213.     cout << DistanceLineSegment(C, D, A, B) << endl;
  214.     cout << DistanceRayPoint(A, B, C) << endl;
  215.     cout << DistanceRaySegment(A, B, C, D) << endl;
  216.     cout << DistanceRays(A, B, C, D) << endl;
  217.     cout << DistanceRayLine(A, B, C, D) << endl;
  218.     cout << Distance(C, A, B) << endl;
  219.     cout << DistanceLineSegment(A, B, C, D) << endl;
  220.     cout << DistanceRayLine(C, D, A, B) << endl;
  221.     Line AB = makeLine(A, B);
  222.     Line CD = makeLine(C, D);
  223.     if (checkParallel(AB, CD))
  224.         cout << Distance(A, C, D) << endl;
  225.     else
  226.         cout << 0 << endl;
  227.     return 0;
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement