Advertisement
999ms

Untitled

Apr 12th, 2020
594
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using i32 = int32_t;
  4. using ui32 = uint32_t;
  5. using i64 = int64_t;
  6. using ui64 = uint64_t;
  7.  
  8. using namespace std;
  9.  
  10.  
  11. i32 main() {
  12.   ios_base::sync_with_stdio(false);
  13.   cin.tie(nullptr);
  14.   cout.tie(nullptr);
  15.   int n;
  16.   cin >> n;
  17.   vector<pair<int,int>> arr(n);
  18.   int mnx = 1e6;
  19.   int mny = 1e6;
  20.   int mxx = -1e6;
  21.   int mxy = -1e6;
  22.   for (int i = 0; i < n; i++) {
  23.     int x, y;
  24.     cin >> x >> y;
  25.     arr[i] = {x, y};
  26.    
  27.     mnx = min(mnx, x - 1);
  28.     mny = min(mny, y - 1);
  29.    
  30.     mxx = max(mxx, x + 1);
  31.     mxy = max(mxy, y + 1);
  32.   }
  33.  
  34.   pair<int,int> A = {mnx, mny},
  35.                 B = {mnx, mxy},
  36.                 C = {mxx, mxy},
  37.                 D = {mxx, mxy};
  38.   double answer = (mxx - mnx) * 2 + (mxy - mny) * 2;
  39.  
  40.   {
  41.     int k = 1e7;
  42.     for (int i = 0; i < n; i++) {
  43.       int x = arr[i].first;
  44.       int y = arr[i].second;
  45.       x -= A.first;
  46.       y -= A.second;
  47.       k = min(k, x + y - 1);
  48.     }
  49.     answer -= k * 2;
  50.     answer += k * sqrt(2);
  51.   }
  52.  
  53.  
  54.   {
  55.     for (int i = 0; i < n; i++) {
  56.       arr[i].second = mxy - arr[i].second;
  57.     }
  58.     B.second = mxy - B.second;
  59.  
  60.     int k = 1e7;
  61.     for (int i = 0; i < n; i++) {
  62.       int x = arr[i].first;
  63.       int y = arr[i].second;
  64.       x -= B.first;
  65.       y -= B.second;
  66.       k = min(k, x + y - 1);
  67.     }
  68.     answer -= k * 2;
  69.     answer += k * sqrt(2);
  70.    
  71.     for (int i = 0; i < n; i++) {
  72.       arr[i].second = mxy - arr[i].second;
  73.     }
  74.   }
  75.  
  76.   {
  77.     for (int i = 0; i < n; i++) {
  78.       arr[i].second = mxy - arr[i].second;
  79.       arr[i].first = mxx - arr[i].first;
  80.     }
  81.  
  82.     C.first = 0;
  83.     C.second = 0;
  84.    
  85.     int k = 1e7;
  86.     for (int i = 0; i < n; i++) {
  87.       int x = arr[i].first;
  88.       int y = arr[i].second;
  89.       x -= B.first;
  90.       y -= B.second;
  91.       k = min(k, x + y - 1);
  92.     }
  93.     answer -= k * 2;
  94.     answer += k * sqrt(2);
  95.    
  96.     for (int i = 0; i < n; i++) {
  97.       arr[i].second = mxy - arr[i].second;
  98.       arr[i].first = mxx - arr[i].first;
  99.     }
  100.   }
  101.  
  102.  
  103.   {
  104.     for (int i = 0; i < n; i++) {
  105.       arr[i].first = mxx - arr[i].first;
  106.     }
  107.     D.first = 0;
  108.    
  109.     int k = 1e7;
  110.     for (int i = 0; i < n; i++) {
  111.       int x = arr[i].first;
  112.       int y = arr[i].second;
  113.       x -= B.first;
  114.       y -= B.second;
  115.       k = min(k, x + y - 1);
  116.     }
  117.     answer -= k * 2;
  118.     answer += k * sqrt(2);
  119.  
  120.     for (int i = 0; i < n; i++) {
  121.       arr[i].first = mxx - arr[i].first;
  122.     }
  123.   }
  124.  
  125.  
  126.   cout << fixed << setprecision(15) << answer << endl;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement