Advertisement
ivnikkk

Untitled

Feb 9th, 2022
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.14 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. //#include "geometry.h"
  4. //#include "data_structure.h"
  5. using namespace std;
  6. using namespace chrono;
  7. #define all(a) a.begin(), a.end()
  8. #define allr(a) a.rbegin(), a.rend()
  9. #define sqrt(x) sqrtl(x)
  10. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  11. typedef long long ll;
  12. typedef double ld;
  13. const ld EPS = 1e-10;
  14.  
  15. #define Vec Point
  16.  
  17. int sign(ld x) {
  18.     if (x > EPS) return 1;
  19.     if (x < -EPS) return -1;
  20.     return 0;
  21. }
  22.  
  23. ld sq(ld x) {
  24.     return x * x;
  25. }
  26.  
  27. struct Point {
  28.     ld x, y;
  29.     Point() : x(0), y(0) {}
  30.     Point(ld _x, ld _y) : x(_x), y(_y) {}
  31.     Point operator-(const Point& other) const {
  32.         return Point(x - other.x, y - other.y);
  33.     }
  34.     Point operator+(const Point& other) const {
  35.         return Point(x + other.x, y + other.y);
  36.     }
  37.     Point operator*(const ld& other) const {
  38.         return Point(x * other, y * other);
  39.     }
  40.     // векторное произведение sin
  41.     ld operator^(const Point& other) const {
  42.         return x * other.y - y * other.x;
  43.     }
  44.     // скалярное произведение cos
  45.     ld operator*(const Point& other) const {
  46.         return x * other.x + y * other.y;
  47.     }
  48.     ld len2() const {
  49.         return sq(x) + sq(y);
  50.     }
  51.     ld len() const {
  52.         return sqrt(len2());
  53.     }
  54.     Point norm() const {
  55.         ld d = len();
  56.         return Point(x / d, y / d);
  57.     }
  58.     bool operator<(const Point& other) const {
  59.         if (sign(x - other.x) != 0) {
  60.             return x < other.x;
  61.         }
  62.         else if (sign(y - other.y) != 0) {
  63.             return y < other.y;
  64.         }
  65.         return false;
  66.     }
  67.     bool operator==(const Point& other) const {
  68.         return sign(x - other.x) == 0 && sign(y - other.y) == 0;
  69.     }
  70.     Point ort() {
  71.         return Point(-y, x);
  72.     }
  73.     void deb() const {
  74.         std::cerr << "(" << x << ", " << y << ")" << std::endl;
  75.     }
  76. };
  77.  
  78. struct Line {
  79.     ld a, b, c;
  80.     Line() : a(0), b(0), c(0) {}
  81.     Line(const Point& x, const Point& y) : a(y.y - x.y), b(x.x - y.x), c(x.y* y.x - y.y * x.x) {
  82.         //// нормирование прямой
  83.         ld d = Point(a, b).len();
  84.         a /= d, b /= d, c /= d;
  85.         if (sign(a) == -1) {
  86.             a = -a;
  87.             b = -b;
  88.             c = -c;
  89.         }
  90.         else if (sign(a) == 0 && sign(b) == 0) {
  91.             a = 0;
  92.             b = -b;
  93.             c = -b;
  94.         }
  95.     }/*
  96.     Line norm() {
  97.         ld d =
  98.     }*/
  99.     //ax+by+c=0
  100.     ////y=-c/b
  101.     //Line norm() {
  102.     // 
  103.     //}
  104.     Point get() {
  105.         if (sign(b) != 0) {
  106.             return Point(0, -c / b);
  107.         }
  108.         else
  109.             return Point(0, -c);
  110.     }
  111.  
  112.     bool operator==(const Line& other) const {
  113.         return sign(a - other.a) == 0 && sign(b - other.b) == 0 && sign(c-other.c)==0;
  114.     }
  115. };
  116.  
  117. //расстояние от точки до точки
  118. ld dist_points(Point& a, Point& b) {
  119.     return sqrtl(sq(a.x - b.x) + sq(a.y - b.y));
  120. }
  121.  
  122. // угол между двумя векторами в радианах
  123. ld get_angle(const Vec& a, const Vec& b) {
  124.     return atan2(a ^ b, a * b);
  125. }
  126.  
  127. // проверка принадлежности точки отрезку
  128. bool is_point_on_seg(const Point& a, const Point& b, const Point& x) {
  129.     // проверка в тупую
  130.     return sign((a - b).len() - (a - x).len() - (b - x).len()) == 0;
  131.     //if (a == b) {
  132.     //  return a == x;
  133.     //}
  134.     //else if (a == x || b == x) {
  135.     //  return true;
  136.     //}
  137.     //else {
  138.     //  return sign((x - a) ^ (b - a)) == 0 &&
  139.     //      sign((x - a) * (b - a)) == 1 &&
  140.     //      sign((x - b) * (a - b)) == 1;
  141.     //}
  142. }
  143. ld dist_line(const Point& a, const Line& l) {
  144.     return abs(l.a * a.x + l.b * a.y + l.c) / sqrt(sq(l.a) + sq(l.b));
  145. }
  146. ld get_dist_line(Point& a, Point& c, Point& d) {
  147.     Line buf(c, d);
  148.     return dist_line(a, buf);
  149. }
  150. ld dist_point_segment(Point& x, Point& c, Point& d) {
  151.     Line check(c, d);
  152.     ld dis = dist_line(x, check);
  153.     Vec k(check.a, check.b);
  154.     k = k * dis;
  155.     Point suba = x + k;
  156.     Point subb = x - k;
  157.     //dis = dist_points(suba, a);
  158.     if (is_point_on_seg(c, d, suba) || is_point_on_seg(c, d, subb)) {
  159.         return dis;
  160.     }
  161.     else {
  162.         return min(dist_points(x, c), dist_points(x, d));
  163.     }
  164. }
  165. ld get_dist_luch(Point& a, Point& c, Point& d) {
  166.     Vec  my = (d - c);
  167.     Vec sec = (a - c);
  168.     if (sign(sec * my) <= 0) {
  169.         return dist_points(a, c);
  170.     }
  171.     else {
  172.         return get_dist_line(a, c, d);
  173.     }
  174. }
  175. bool cmp(Point& lht, Point& rht) {
  176.     if (fabs(lht.x - rht.x) <= EPS) {
  177.         return  lht.y < rht.y;
  178.     }
  179.     return lht.x < rht.x;
  180. }
  181. bool line_cross(const Line& a, const Line& b, Point& ans) {
  182.     ld d = (a.b * b.a - a.a * b.b);
  183.     if (sign(d) == 0)
  184.         return false;
  185.     ans.x = (b.b * a.c - b.c * a.b) / d;
  186.     ans.y = (b.c * a.a - a.c * b.a) / d;
  187.     return true;
  188. }
  189. bool segment_cross(const Point& a, const Point& b, const Point& c, const Point& d) {
  190.     if (sign((a - b) ^ (c - d)) == 0) {
  191.         return is_point_on_seg(a, b, c) ||
  192.             is_point_on_seg(a, b, d) ||
  193.             is_point_on_seg(c, d, a) ||
  194.             is_point_on_seg(c, d, b);
  195.     }
  196.     Point ans;
  197.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  198.         return is_point_on_seg(a, b, ans) && is_point_on_seg(c, d, ans);
  199.     }
  200. }
  201. ld dist_seg_to_seg(Point a, Point b, Point c, Point d) {
  202.     if (segment_cross(a, b, c, d)) {
  203.         return 0;
  204.     }
  205.     return min(min(dist_point_segment(a, c, d), dist_point_segment(b, c, d)), min(dist_point_segment(c, a, b), dist_point_segment(d, a, b)));
  206.     /*if (!cmp(a, b)) {
  207.         swap(a, b);
  208.     }
  209.     if (!cmp(c, d)) {
  210.         swap(c, d);
  211.     }
  212.  
  213.     if (segment_cross(a, b, c, d)) {
  214.         return 0;
  215.     }
  216.     if (sign((d-a) * (b-a)) <= 0) {
  217.         return dist_points(d, a);
  218.     }
  219.     if (sign((a - b) * (c-b)) <= 0) {
  220.         return dist_points(b, c);
  221.     }
  222.     return min(min(dist_point_segment(a, c, d), dist_point_segment(b, c, d)), min(dist_point_segment(c, a, b), dist_point_segment(d, a, b)));*/
  223. }
  224. ld get_dist_seg_to_lunch(Point a, Point b, Point c, Point d) {
  225.     Point ans;
  226.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  227.         if (is_point_on_seg(a, b, ans) && sign((ans - c) * (d - c)) == 1) {
  228.             return 0;
  229.         }
  230.     }
  231.     // проверить на равенство прямых
  232.     if (sign((b - c) * (d - c)) <= 0 && sign((a - c) * (d - c)) <= 0) {
  233.         return min(dist_points(c, b), dist_points(c, a));
  234.     }
  235.     else {
  236.         return min(dist_point_segment(c, a, b), min(get_dist_luch(a, c, d), get_dist_luch(b, c, d)));
  237.     }
  238. }
  239. ld dist_seg_line(Point a, Point b, Point c, Point d) {
  240.     Point ans;
  241.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  242.         if (is_point_on_seg(a, b, ans))
  243.             return 0;
  244.     }
  245.     return min(dist_line(a, Line(c, d)), dist_line(b, Line(c, d)));
  246. }
  247.  
  248. bool check(Line lht, Line rht) {
  249.     return lht==rht;
  250. }
  251. ld dist_luch_to_luch(Point& a, Point& b, Point& c, Point& d) {
  252.     Point ans;
  253.     if ((sign((b - a) ^ (d - c)) == 0)) {
  254.         if (check(Line(a, b), Line(c, d))) {
  255.             //a  c  b  d
  256.             if (is_point_on_seg(a, b, c)) {
  257.                 return 0;
  258.             }
  259.         }
  260.         return min(get_dist_luch(a, c, d), get_dist_luch(c, a, b));
  261.     }
  262.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  263.         if (sign((ans - c) * (d - c)) == 1 && sign((ans - a) * (b - a)) == 1) {
  264.             return 0;
  265.         }
  266.     }
  267.     return min(dist_points(a, c), min(get_dist_luch(a, c, d), get_dist_luch(c, a, b)));
  268. }
  269. ld dist_luch_to_line(Point& a, Point& b, Point& c, Point& d) {
  270.     if (sign((b - a) ^ (d - c)) == 0) {
  271.         if (check(Line(a, b), Line(c, d))) {
  272.             return 0;
  273.         }
  274.         return dist_line(a, Line(c, d));
  275.     }
  276.     Point ans;
  277.     line_cross(Line(a, b), Line(c, d), ans);
  278.     if (sign((ans - a) * (b - a)) == 1)
  279.         return 0;
  280.     else return dist_line(a, Line(c, d));
  281. }
  282. //
  283. //ld dist_line_to_line(Point& a, Point& b, Point& c, Point& d) {
  284. //  Line l1(a, b), l2(c, d);
  285. //  Point ans;
  286. //  if (line_cross(l1, l2,ans))return 0.000000;
  287. //  return fabs(l1.c - l2.c) / sqrtl(sq(l1.a) + sq(l1.b));
  288. //}
  289. ld dist_line_to_line(Point& a, Point& b, Point& c, Point& d) {
  290.     Point ans;
  291.     if (line_cross(Line(a, b), Line(c, d), ans)) {
  292.         return 0;
  293.     }
  294.     Point sub = Line(a, b).get();
  295.     if (check(Line(a, b), Line(c, d))) {
  296.         return 0;
  297.     }
  298.     return dist_line(sub, Line(c, d));
  299. }
  300. signed main() {
  301. #ifdef _DEBUG
  302.     freopen("input.txt", "r", stdin);
  303.     freopen("output.txt", "w", stdout);
  304. #endif
  305.     srand(time(NULL));
  306.     ios_base::sync_with_stdio(false);
  307.     cin.tie(nullptr);
  308.     cout.tie(nullptr);
  309.     cout << fixed << setprecision(10);
  310.     Point a, b, c, d;
  311.     cin >> a.x >> a.y;
  312.     cin >> b.x >> b.y;
  313.     cin >> c.x >> c.y;
  314.     cin >> d.x >> d.y;
  315.     //cout << dist_seg_to_seg(a, b, c, d) << '\n';
  316.     cout << dist_points(a, c) << '\n';
  317.     // a  [c,d];
  318.     cout << dist_point_segment(a, c, d) << '\n';
  319.     // a [(c,d),inf)
  320.     cout << get_dist_luch(a, c, d) << '\n';
  321.     //a (-inf,(c,d),inf)
  322.     cout << get_dist_line(a, c, d) << '\n';
  323.     // c [a,b]
  324.     cout << dist_point_segment(c, a, b) << '\n';
  325.     //[a,b] ; [c,d];
  326.     cout << dist_seg_to_seg(a, b, c, d) << '\n';
  327.     //cout << "расстояние от отрезка до лучаа" << endl;
  328.     cout << get_dist_seg_to_lunch(a, b, c, d) << '\n';
  329.     //расстояние от прямой до отрезка
  330.     cout << dist_seg_line(a, b, c, d) << '\n';
  331.     cout << get_dist_luch(c, a, b) << '\n';
  332.     cout << get_dist_seg_to_lunch(c, d, a, b) << '\n';
  333.     //расстояние от луча до луча
  334.     cout << dist_luch_to_luch(a, b, c, d) << '\n';
  335.     //расстояние от луча до прямой
  336.     cout << dist_luch_to_line(a, b, c, d) << '\n';
  337.     // расстояние от прямой до точки
  338.     cout << get_dist_line(c, a, b) << '\n';
  339.     cout << dist_seg_line(c, d, a, b) << '\n';
  340.     //cout << ((b - a) ^ (d - c));
  341.     cout << dist_luch_to_line(c, d, a, b) << '\n';
  342.     cout << dist_line_to_line(a, b, c, d) << '\n';
  343.  
  344. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement