Advertisement
Guest User

Untitled

a guest
Apr 10th, 2020
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <utility>
  6. #include <climits>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. double dist(pair<int, int> a, pair<int, int> b)
  12. {
  13.     long long int x = (a.first - b.first);
  14.     long long int y = (a.second - b.second);
  15.     return sqrt(x * x + y * y);
  16. }
  17.  
  18. int main()
  19. {
  20.     int N;
  21.     cin >> N;
  22.     vector<pair<int, int>> dots;
  23.  
  24.     int min_x = 100000000;
  25.     int max_x = -100000000;
  26.     int min_y = 100000000;
  27.     int max_y = -100000000;
  28.  
  29.  
  30.     for (int i = 0; i < N; i++) {
  31.         int x, y;
  32.         cin >> x >> y;
  33.         dots.push_back(pair<int, int>{x, y});
  34.         if (x < min_x) {
  35.             min_x = x;
  36.         } else if (x > max_x) {
  37.             max_x = x;
  38.         }
  39.         if (y < min_y) {
  40.             min_y = y;
  41.         } else if (y > max_y) {
  42.             max_y = y;
  43.         }
  44.     }
  45.     vector<pair<int, int>> coords = {{min_x - 1, min_y - 1},
  46.                                      {min_x - 1, max_y + 1},
  47.                                      {max_x + 1, max_y + 1},
  48.                                      {max_x + 1, min_y - 1}};
  49.  
  50.     vector<pair<int, int>> external = {{INT_MAX, INT_MAX},
  51.                                        {INT_MAX, INT_MAX},
  52.                                        {INT_MAX, INT_MAX},
  53.                                        {INT_MAX, INT_MAX}};
  54.     for (size_t i = 0; i < dots.size(); i++) {
  55.         for (int j = 0; j < 4; j++) {
  56.             if (dist(coords[j], dots[i]) < dist(coords[j], external[j])) {
  57.                 external[j] = dots[i];
  58.             }
  59.         }
  60.     }
  61.     double P = (max_x + 1 - min_x + 1) * 2 + (max_y + 1 - min_y + 1) * 2;
  62.     for (int i = 0; i < 4; i++) {
  63.         int a = abs(coords[i].first - external[i].first);
  64.         int b = abs(coords[i].second - external[i].second);
  65.         P = P - 2 * (a + b - 1) + (a + b - 1) * sqrt(2);
  66.     }
  67.     cout << P;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement