Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. struct Vect
  9. {
  10.     long double x, y;
  11.  
  12.     Vect(long double _x = 0, long double _y = 0) : x(_x), y(_y){}
  13.     Vect(const Vect &p) : x(p.x), y(p.y){}
  14.  
  15.     Vect operator +(const Vect &other) const
  16.     {
  17.         return {x + other.x, y + other.y};
  18.     }
  19.  
  20.     Vect operator -(const Vect &other) const
  21.     {
  22.         return {x - other.x, y - other.y};
  23.     }
  24.  
  25.     long double operator *(const Vect &other) const
  26.     {
  27.         return x * other.x + y * other.y;
  28.     }
  29.  
  30.     long double operator %(const Vect &other) const
  31.     {
  32.         return x * other.y - y * other.x;
  33.     }
  34. };
  35.  
  36.  
  37. istream& operator >> (istream &in, Vect &v)
  38. {
  39.     in >> v.x >> v.y;
  40.     return in;
  41. }
  42.  
  43. ostream& operator << (ostream &out, const Vect &v)
  44. {
  45.     out << v.x << " " << v.y;
  46.     return out;
  47. }
  48.  
  49.  
  50. struct Line
  51. {
  52.     Vect p, d;
  53.  
  54.     Line(Vect &f, Vect &s) : p(f), d(s - f){}
  55. };
  56.  
  57. bool is_in(Vect &A, Vect &B, Vect &C)
  58. {
  59.     return (A.x - C.x) * (B.x - C.x) <= 0 && (A.y - C.y) * (B.y - C.y) <= 0 && (C - A) % (C - B) == 0;
  60. }
  61.  
  62. vector <Vect> points;
  63. int ind_left = 0;
  64.  
  65. long double Distance(Vect a)
  66. {
  67.     return sqrt(a.x * a.x + a.y * a.y);
  68. }
  69.  
  70. bool cmp(Vect a, Vect b)
  71. {
  72.     return (a - points[ind_left]) % (b - points[ind_left]) > 0 ||
  73.            ((a - points[ind_left]) % (b - points[ind_left]) == 0 &&
  74.             Distance((a - points[ind_left])) < Distance((b - points[ind_left])));
  75. }
  76.  
  77. int main()
  78. {
  79.     int n;
  80.     cin >> n;
  81.     vector <pair<long double, long double>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
  82.     for (int i = 0; i < n; i++)
  83.     {
  84.         Vect t, d;
  85.         cin >> t;
  86.         points.push_back(t);
  87.         for (auto dir: directions) {
  88.             d.x = t.x + dir.first;
  89.             d.y = t.y + dir.second;
  90.             points.push_back(d);
  91.         }
  92.     }
  93.     n = points.size();
  94.     for (int i = 0; i < n; i++) /// ----- find min x and min y point
  95.     {
  96.         if (points[i].x < points[ind_left].x ||
  97.             (points[i].x == points[ind_left].x && points[i].y < points[ind_left].y))
  98.         {
  99.             ind_left = i;
  100.         }
  101.     } /// --- end
  102.     // for (int i = 0; i < n; i++){
  103.     //      cout << points[i].x << ' ' << points[i].y << '\n';
  104.     //  }
  105.     vector <Vect> convex_hull;
  106.     convex_hull.push_back(points[ind_left]);
  107.     vector <Vect> sorted; /// without left point !
  108.     for (int i = 0; i < n; i++)
  109.     {
  110.         if (i != ind_left)
  111.         {
  112.             sorted.push_back(points[i]);
  113.         }
  114.     }
  115.  
  116.     sort(sorted.begin(), sorted.end(), cmp);
  117.     if (sorted.size() > 0){
  118.         convex_hull.push_back(sorted[0]);
  119.     }
  120.  
  121.  
  122.     for (int i = 1; i < sorted.size(); i++) /// take points
  123.     {
  124.         Vect last_vec = convex_hull.back();
  125.         //convex_hull.pop_back();
  126.         Vect prev_last = convex_hull[convex_hull.size() - 2];
  127.         //convex_hull.pop_back();
  128.         while (convex_hull.size() > 1 && (last_vec - prev_last) % (sorted[i] - last_vec) <= 0)
  129.         {
  130.             convex_hull.pop_back();
  131.             last_vec = prev_last;
  132.             prev_last = convex_hull[convex_hull.size() - 2];
  133.             //prev_last = convex_hull.back();
  134.             //convex_hull.pop_back();
  135.         }
  136.  
  137.         //convex_hull.push_back(prev_last);
  138.         //if ((last_vec - prev_last) % (sorted[i] - last_vec) > 0){
  139.         //    convex_hull.push_back(last_vec);
  140.         //}
  141.  
  142.         convex_hull.push_back(sorted[i]);
  143.     }
  144.  
  145.     long double P = 0;
  146.     Vect last_vec = points[ind_left];
  147.  
  148.     while (!convex_hull.empty()) {
  149.         long double distx = abs(convex_hull.back().x - last_vec.x);
  150.         long double disty = abs(convex_hull.back().y - last_vec.y);
  151.         P += abs(distx - disty);
  152.         P += Distance(Vect(min(distx, disty), min(distx, disty)));
  153.         if (convex_hull.size() > 1) {
  154.             last_vec = convex_hull.back();
  155.             convex_hull.pop_back();
  156.         } else {
  157.             convex_hull.pop_back();
  158.         }
  159.     }
  160.  
  161.     cout << setprecision(20) << P;
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement