Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <limits>
  7. #include <iomanip>
  8.  
  9. struct Point;
  10.  
  11. typedef long long ll;
  12. typedef std::vector<Point> vector_of_points;
  13.  
  14. struct StackExtended
  15. {
  16. public:
  17.     void push(size_t x);
  18.     int top();
  19.     int top_next();
  20.     int pop();
  21. public:
  22.     std::vector<size_t> _data;
  23. };
  24.  
  25. struct Point
  26. {
  27.     ll x = -1;
  28.     ll y = -1;
  29.  
  30.     Point();
  31.     Point(ll x, ll y);
  32.     Point(Point const &p);
  33.     Point(Point &&p);
  34.     Point &operator=(Point const &p);
  35.     Point &operator=(Point &&p);
  36.     void swap(Point &p);
  37.     friend std::ostream &operator<<(std::ostream &os, const Point &dt);
  38.     friend bool operator==(Point const &lhs, Point const &rhs);
  39.     friend bool operator!=(Point const &lhs, Point const &rhs);
  40. };
  41.  
  42. Point::Point() = default;
  43.  
  44. Point::Point(ll x, ll y) : x(x), y(y)
  45. {}
  46.  
  47. void Point::swap(Point &p)
  48. {
  49.     Point tmp(std::move(p));
  50.     p = std::move(*this);
  51.     *this = std::move(tmp);
  52. }
  53.  
  54. Point &Point::operator=(Point const &p)
  55. {
  56.     x = p.x;
  57.     y = p.y;
  58.     return *this;
  59. }
  60.  
  61. Point &Point::operator=(Point &&p)
  62. {
  63.     x = p.x;
  64.     y = p.y;
  65.     return *this;
  66. }
  67.  
  68. Point::Point(Point const &p)
  69. {
  70.     x = p.x;
  71.     y = p.y;
  72. }
  73.  
  74. Point::Point(Point &&p)
  75. {
  76.     x = p.x;
  77.     y = p.y;
  78. }
  79.  
  80. std::ostream &operator<<(std::ostream &os, const Point &dt)
  81. {
  82.     os << dt.x << ' ' << dt.y;
  83.     return os;
  84. }
  85.  
  86. bool operator==(Point const &lhs, Point const &rhs)
  87. {
  88.     return lhs.x == rhs.x && lhs.y == rhs.y;
  89. }
  90.  
  91. bool operator!=(Point const &lhs, Point const &rhs)
  92. {
  93.     return !(lhs == rhs);
  94. }
  95.  
  96. void StackExtended::push(size_t x)
  97. {
  98.     _data.push_back(x);
  99. }
  100.  
  101. int StackExtended::top()
  102. {
  103.     if (_data.empty())
  104.     { return -1; }
  105.     return int(_data[_data.size() - 1]);
  106. }
  107.  
  108. int StackExtended::top_next()
  109. {
  110.     if (_data.size() < 2)
  111.     { return -1; }
  112.     return int(_data[_data.size() - 2]);
  113. }
  114.  
  115. int StackExtended::pop()
  116. {
  117.     if (_data.empty())
  118.     { return -1; }
  119.     int tmp = top();
  120.     _data.pop_back();
  121.     return tmp;
  122. }
  123.  
  124. ll distance_pow2(ll x1, ll y1, ll x2, ll y2)
  125. {
  126.     return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  127. }
  128.  
  129. ll cross(size_t next_to_top, size_t top, size_t pi, vector_of_points const &data)
  130. {
  131.     Point u = {data[top].x - data[next_to_top].x,
  132.                data[top].y - data[next_to_top].y};
  133.     Point v = {data[pi].x - data[top].x,
  134.                data[pi].y - data[top].y};
  135.     return u.x * v.y - u.y * v.x;
  136. }
  137.  
  138.  
  139. ll cross(Point next_to_top, Point top, Point pi)
  140. {
  141.     Point u = {top.x - next_to_top.x,
  142.                top.y - next_to_top.y};
  143.     Point v = {pi.x - top.x,
  144.                pi.y - top.y};
  145.     return u.x * v.y - u.y * v.x;
  146. }
  147.  
  148. bool left_directed(size_t next_to_top, size_t top, size_t pi, vector_of_points const &data)
  149. {
  150.     return cross(next_to_top, top, pi, data) <= 0;
  151. }
  152.  
  153. StackExtended _stack;
  154.  
  155. vector_of_points const &graham(vector_of_points const &points)
  156. {
  157.     auto *ret = new vector_of_points();
  158.     switch (points.size())
  159.     {
  160.         case 0:
  161.         case 1:
  162.             return *ret;
  163.         case 2:
  164.             ret->emplace_back(points[0].x, points[0].y);
  165.             ret->emplace_back(points[1].x, points[1].y);
  166.             return *ret;
  167.         default:
  168.             break;
  169.     }
  170.     vector_of_points data_counter_clock_from_p0 = points;
  171.     auto it_to_min_y_element = std::min_element(data_counter_clock_from_p0.begin(),
  172.                                                 data_counter_clock_from_p0.end(),
  173.                                                 [](const Point &a, const Point &b)
  174.                                                 {
  175.                                                     return a.y < b.y;
  176.                                                 });
  177.  
  178.     data_counter_clock_from_p0.begin()->swap(*it_to_min_y_element);
  179.     ll x0 = data_counter_clock_from_p0[0].x;
  180.     ll y0 = data_counter_clock_from_p0[0].y;
  181.     std::sort(data_counter_clock_from_p0.begin() + 1, data_counter_clock_from_p0.end(), [x0, y0](const Point &a,
  182.                                                                                                  const Point &b)
  183.     {
  184.         Point at{a.y - y0, a.x - x0};
  185.         Point bt{b.y - y0, b.x - x0};
  186.         ll cross = at.x * bt.y - at.y * bt.x;
  187.         if (cross == 0)
  188.         {
  189.             ll dis_a_p0 = distance_pow2(a.x, a.y, x0, y0);
  190.             ll dis_b_p0 = distance_pow2(b.x, b.y, x0, y0);
  191.             return dis_a_p0 < dis_b_p0;
  192.         } else
  193.         {
  194.             return cross < 0;
  195.         }
  196.     });
  197.     _stack.push(0);
  198.     _stack.push(1);
  199.     for (size_t pi = 2; pi < data_counter_clock_from_p0.size(); pi++)
  200.     {
  201.         int _next_to_top = _stack.top_next();
  202.         assert(_next_to_top != -1);
  203.         int _top = _stack.top();
  204.         assert(_top != -1);
  205.         while (left_directed(size_t(_next_to_top), size_t(_top), pi, data_counter_clock_from_p0))
  206.         {
  207.             _stack.pop();
  208.             if (_stack._data.size() == 1) break;
  209.             _next_to_top = _stack.top_next();
  210.             assert(_next_to_top != -1);
  211.             _top = _stack.top();
  212.             assert(_top != -1);
  213.         }
  214.         _stack.push(pi);
  215.     }
  216.     for (size_t i = 0; i < _stack._data.size(); i++) //NOLINT
  217.     {
  218.         ret->push_back(data_counter_clock_from_p0[_stack._data[i]]);
  219.     }
  220.     _stack._data.clear();
  221.     return *ret;
  222. }
  223.  
  224.  
  225. int main()
  226. {
  227.     int N;
  228.     std::cin >> N;
  229.     vector_of_points data;
  230.     for (int i = 0; i < N; ++i)
  231.     {
  232.         int x, y;
  233.         std::cin >> x >> y;
  234.         data.emplace_back(x, y);
  235.     }
  236.     std::sort(data.begin(), data.end(), [](const Point &a, const Point &b)
  237.     {
  238.         if (a.x == b.x) return a.y <= b.y;
  239.         return a.x < b.x;
  240.     });
  241.  
  242.     vector_of_points to;
  243.     if (!data.empty()) to.emplace_back(data[0].x, data[0].y);
  244.     for (int i = 1; i < data.size(); i++)
  245.     {
  246.         if (data[i] != data[i - 1])
  247.         {
  248.             to.emplace_back(data[i].x, data[i].y);
  249.         }
  250.     }
  251.  
  252.     const vector_of_points &ans = graham(to);
  253.     int sz = int(ans.size());
  254.     double dist_pow2 = 0;
  255.     int index_low = 0;
  256.     auto it_to_max_y_element = std::max_element(ans.begin(), ans.end(),
  257.                                                 [](const Point &a, const Point &b)
  258.                                                 {
  259.                                                     return a.y < b.y;
  260.                                                 });
  261.     int index_high = static_cast<int>(std::distance(ans.begin(), it_to_max_y_element));
  262.     int iter_from_high = index_high;
  263.     int iter_from_low = index_low;
  264.  
  265.     while (iter_from_high != index_low || iter_from_low != index_high)
  266.     {
  267.         double dist_pow2_tmp = distance_pow2(ans[iter_from_low].x, ans[iter_from_low].y,
  268.                                   ans[iter_from_high].x, ans[iter_from_high].y);
  269.         dist_pow2 = std::max(dist_pow2, dist_pow2_tmp);
  270.         /**
  271.          *    ...<--
  272.          *
  273.          *
  274.          *        -->...
  275.          */
  276.         Point lowv = ans[iter_from_low];
  277.         Point lowv_next = ans[(iter_from_low + 1) % sz];
  278.  
  279.         Point upv = ans[iter_from_high];
  280.         Point upv_next = ans[(iter_from_high + 1) % sz];
  281.         Point delta_up = {upv_next.x - upv.x, upv_next.y - upv.y};
  282.         Point delta_up_from_lownext = {delta_up.x + lowv_next.x, delta_up.y + lowv_next.y};
  283.         ll rot = cross(lowv, lowv_next, delta_up_from_lownext);
  284.         if (rot < 0)
  285.         {
  286.             iter_from_low++;
  287.             iter_from_low %= sz;
  288.         }
  289.         else if (rot > 0)
  290.         {
  291.             iter_from_high++;
  292.             iter_from_high %= sz;
  293.         }
  294.         else
  295.         {
  296.             iter_from_low++;
  297.             iter_from_low %= sz;
  298.             iter_from_high++;
  299.             iter_from_high %= sz;
  300.         }
  301.     }
  302.     std::cout << std::setprecision(std::numeric_limits<double>::max_digits10) << sqrt(dist_pow2);
  303.     return 0;
  304. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement