Advertisement
TimSenin

Untitled

Oct 17th, 2022
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. struct Dot {
  4.     Dot() = default;
  5.  
  6.     Dot(long double x, long double y) : x(x), y(y) {}
  7.  
  8.     Dot operator-(Dot other) const {
  9.         return {x - other.x, y - other.y};
  10.     }
  11.  
  12.     Dot operator+(Dot other) const {
  13.         return {x + other.x, y + other.y};
  14.     }
  15.  
  16.     Dot operator*(Dot other) const {
  17.         return {x * other.x, y * other.y};
  18.     }
  19.  
  20.     Dot operator/(Dot other) const {
  21.         return {x / other.x, y / other.y};
  22.     }
  23.  
  24.     Dot operator-() const {
  25.         return {-x, -y};
  26.     }
  27.  
  28.     bool operator==(Dot other) const {
  29.         return std::abs(x - other.x) < 0.00001 && std::abs(y - other.y) < 0.00001;
  30.     }
  31.  
  32.     long double x;
  33.     long double y;
  34. };
  35.  
  36. struct Line {
  37.     Line(long double x1, long double y1, long double x2, long double y2) : a(y1 - y2), b(x2 - x1),
  38.                                                                            c(x1 * (y2 - y1) - y1 * (x2 - x1)) {};
  39.  
  40.     Line(long double a, long double b, long double c) : a(a), b(b), c(c) {}
  41.  
  42.     long double a;
  43.     long double b;
  44.     long double c;
  45. };
  46.  
  47. double scal_prod(Dot first, Dot second) {
  48.     return first.x * second.x + first.y * second.y;
  49. }
  50.  
  51. double skew_prod(Dot first, Dot second) {
  52.     return first.x * second.y - second.x * first.y;
  53. }
  54.  
  55. bool IsDotInsideSegment(Dot target, Dot a, Dot b) {
  56.     Dot p1p2 = b - a;
  57.     Dot p1m = target - a;
  58.     Dot mp1 = a - target;
  59.     Dot mp2 = b - target;
  60.     if (skew_prod(p1p2, p1m) == 0 && scal_prod(mp1, mp2) <= 0) {
  61.         return true;
  62.     } else {
  63.         return false;
  64.     }
  65. }
  66.  
  67. bool AreDotsOnDiffSides(Dot p1, Dot p2, Dot m1, Dot m2) {
  68.     Dot p1p2 = p2 - p1;
  69.     Dot p1m2 = m2 - p1;
  70.     Dot p1m1 = m1 - p1;
  71.     if (skew_prod(p1p2, p1m2) * skew_prod(p1p2, p1m1) < 0) {
  72.         return true;
  73.     } else {
  74.         return false;
  75.     }
  76. }
  77.  
  78. std::vector<Dot> Graham(std::vector<Dot>& dots) {
  79.     Dot start = dots.front();
  80.     for (Dot d : dots) {  // ищем старт
  81.         if (d.x < start.x || (d.x == start.x && d.y < start.y)) {
  82.             start = d;
  83.         }
  84.     }
  85.  
  86.     for (Dot& d : dots) {  // делаем start началом координат
  87.         d.x -= start.x;
  88.         d.y -= start.y;
  89.     }
  90.  
  91.     std::sort(dots.begin(), dots.end(), [&](Dot a, Dot b) {  // сортим точки по полярному углу
  92.         return skew_prod(a, b) > 0 || skew_prod(a, b) == 0 && a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
  93.     });
  94.  
  95.     std::vector<Dot> stack;
  96.     for (Dot d : dots) {
  97.         while (stack.size() >= 2) {
  98.             Dot last = d - stack.back();
  99.             Dot pre_last = stack[stack.size() - 2] - stack.back();
  100.             if (skew_prod(last, pre_last) <= 0) {
  101.                 stack.pop_back();
  102.             } else {
  103.                 break;
  104.             }
  105.         }
  106.         stack.push_back(d);
  107.     }
  108.     return stack;
  109. }
  110.  
  111. long double count_square(std::vector<Dot>& dots) {
  112.     long double square = 0;
  113.     for (int i = 0; i < dots.size() - 1; ++i) {
  114.         square += skew_prod(dots[i], dots[i+1]);
  115.     }
  116.     square += skew_prod(dots.back(), dots.front());
  117.     square = square / 2;
  118.     return std::abs(square);
  119. }
  120.  
  121. long double count_perimeter(std::vector<Dot>& dots) {
  122.     long double perimeter = 0;
  123.     for (int i = 0; i < dots.size() - 1; ++i) {
  124.         perimeter += sqrt(std::pow(dots[i+1].x - dots[i].x, 2) + std::pow(dots[i+1].y - dots[i].y, 2));
  125.     }
  126.     perimeter += sqrt(std::pow(dots.back().x - dots.front().x, 2) + std::pow(dots.back().y - dots.front().y, 2));
  127.     return perimeter;
  128. }
  129.  
  130. long double count_distance(Dot first, Dot second) {
  131.     return sqrt(std::pow(first.x - second.x, 2) + std::pow(first.y - second.y, 2));
  132. }
  133.  
  134. int main() {
  135.     long double x, y;
  136.     std::cin >> x >> y;
  137.     long double x1, y1, x2, y2, x3, y3, x4, y4;
  138.     std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
  139.     long double alpha = count_distance(Dot(x1, y1), Dot(x4, y4)) / count_distance(Dot(0, 0), Dot(0, y));
  140.     long double cos = scal_prod(Dot(x, y), Dot(Dot(x3, y3) - Dot(x1, y1))) / (count_distance(Dot(0, 0), Dot(x, y)) * count_distance(Dot(0, 0), Dot(Dot(x3, y3) - Dot(x1, y1))));
  141.     long double sin = skew_prod(Dot(x, y), Dot(Dot(x3, y3) - Dot(x1, y1))) / (count_distance(Dot(0, 0), Dot(x, y)) * count_distance(Dot(0, 0), Dot(Dot(x3, y3) - Dot(x1, y1))));
  142.     Dot prev = Dot(0, 0);
  143.     Dot res = Dot(alpha * (prev.x * cos - prev.y * sin), alpha * (prev.x * sin + prev.y * cos)) + Dot(x1, y1);
  144.     while (res != prev) {
  145.         prev = res;
  146.         res = Dot(alpha * (prev.x * cos - prev.y * sin), alpha * (prev.x * sin + prev.y * cos)) + Dot(x1, y1);
  147.     }
  148.     std::cout << std::setprecision(5) << res.x << std::endl << res.y;
  149.     return 0;
  150. }
  151.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement