fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. const int maxn = 100001;
  7.  
  8. #define x first
  9. #define y second
  10.  
  11. int t,n;
  12. pair<int, int> point[maxn];
  13.  
  14. bool check(int r)
  15. {
  16.     int xL = -100001, xR = 100001;
  17.     int  yL = -100001, yR = 100001;
  18.     int zL = (-100001) << 1, zR = 100001 << 1;
  19.     for(int i = 0; i < n; i++)
  20.     {
  21.         xL = max(xL, point[i].x - r);
  22.         xR = min(xR, point[i].x + r);
  23.         yL = max(yL, point[i].y - r);
  24.         yR = min(yR, point[i].y + r);
  25.         zL = max(zL, point[i].x + point[i].y - r);
  26.         zR = min(zR, point[i].x + point[i].y + r);
  27.     }
  28.     if(xL > xR || yL > yR) return 0;
  29.     zL = max(zL, xL + yL);
  30.     zR = min(zR, xR + yR);
  31.     return zL <= zR;
  32. }
  33. int main()
  34. {
  35.     std::cin >> t;
  36.     int cas = 0;
  37.     while(t--)
  38.     {
  39.         cas++;
  40.         std::cin >> n;
  41.         for(int i = 0; i < n; i++) {
  42.             std::cin >> point[i].x >> point[i].y;
  43.         }
  44.         int L = 0, R = 100001;
  45.         while(L < R)
  46.         {
  47.             int mid = (L + R) >> 1;
  48.             if(check(mid)) R = mid;
  49.             else {
  50.                 L = mid + 1;
  51.             }
  52.         }
  53.         // std::cout << "L=" << L << '\n';
  54.         ll ans = L * (L + 1LL) * 3 + 1;
  55.         printf("Case %d: %lld\n", cas, ans);
  56.     }
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
1
3
0 0 
-1 0
-2 2
stdout
copy 
Case 1: 7
https://ideone.com/YO4n3x
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!