Advertisement
TimSenin

Untitled

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