Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
169
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. // @author: Danielto1404
  7.  
  8. #define c_boost std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr)
  9.  
  10. using namespace std;
  11.  
  12. struct point {
  13.     int x, y;
  14. };
  15.  
  16. double size(point a, point b) {
  17.     int hyp_cnt = min(abs(a.x - b.x), abs(a.y - b.y));
  18.     int max_size = max(abs(a.x - b.x), abs(a.y - b.y));
  19.     return sqrt(2) * hyp_cnt + (max_size - hyp_cnt);
  20. }
  21.  
  22. bool negative(point a, point b, point c) {
  23.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
  24. }
  25.  
  26. bool positive(point a, point b, point c) {
  27.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
  28. }
  29.  
  30. void find_min_shell(vector<point> &points) {
  31.     if (points.size() == 1) return;
  32.  
  33.     sort(points.begin(), points.end(), [](point a, point b) {
  34.         return a.x < b.x || (a.x == b.x && a.y < b.y);
  35.     });
  36.  
  37.     point left = points.front(), right = points.back();
  38.     vector<point> up, down;
  39.     up.push_back(left);
  40.     down.push_back(left);
  41.  
  42.     for (int i = 1; i < points.size(); ++i) {
  43.         if (i == points.size() - 1 || negative(left, points[i], right)) {
  44.             while (up.size() >= 2 && !negative(up[up.size() - 2], up.back(), points[i]))
  45.                 up.pop_back();
  46.  
  47.             up.push_back(points[i]);
  48.         }
  49.         if (i == points.size() - 1 || positive(left, points[i], right)) {
  50.             while (down.size() >= 2 && !positive(down[down.size() - 2], down.back(), points[i]))
  51.                 down.pop_back();
  52.  
  53.             down.push_back(points[i]);
  54.         }
  55.     }
  56.  
  57.     points.clear();
  58.     for (const point p : up)
  59.         points.push_back(p);
  60.  
  61.     for (int i = (int) down.size() - 2; i > 0; --i)
  62.         points.push_back(down[i]);
  63. }
  64.  
  65. int main() {
  66.     c_boost;
  67.     int n, x, y;
  68.     cin >> n;
  69.     vector<point> points;
  70.     for (int i = 0; i < n; ++i) {
  71.         cin >> x >> y;
  72.         points.push_back({x + 1, y});
  73.         points.push_back({x - 1, y});
  74.         points.push_back({x, y + 1});
  75.         points.push_back({x, y - 1});
  76.     }
  77.  
  78.     find_min_shell(points);
  79.  
  80.     double perimeter = 0;
  81.     for (int i = 0; i < points.size() - 1; ++i) {
  82.         perimeter += size(points[i], points[i + 1]);
  83.     }
  84.     perimeter += size(points.back(), points.front());
  85.     cout << perimeter;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement