fork download
copy 
  1. // Author: 4uckd3v - Nguyen Cao Duc
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<ll, ll> ii;
  7.  
  8. const int MAX_N = 3e5;
  9. const int MOD = 1e9 + 7;
  10. const ll INF = 8e18;
  11.  
  12. struct Rect {
  13.     ll x, y, u, v;
  14.  
  15.     Rect() {};
  16.     Rect(ll x, ll y, ll u, ll v) : x(x), y(y), u(u), v(v) {};
  17.  
  18.     Rect empty() const {
  19.         return Rect(-INF, -INF, -INF, -INF);
  20.     };
  21.  
  22.     Rect intersect(const Rect& other) const {
  23.         if (u < other.x || v < other.y) return empty();
  24.  
  25.         Rect ret = Rect(max(x, other.x), max(y, other.y), min(u, other.u), min(v, other.v));
  26.         if (ret.x > ret.u || ret.y > ret.v) return empty();
  27.  
  28.         return ret;
  29.     };
  30.  
  31.     bool operator==(const Rect& other) const {
  32.         return (x == other.x && v == other.v && u == other.u && v == other.v);
  33.     };
  34. };
  35.  
  36. int n;
  37. ii a[MAX_N + 5];
  38.  
  39. ll newRow(ll x, ll y) {
  40.     return x - y;
  41. };
  42.  
  43. ll newCol(ll x, ll y) {
  44.     return x + y;
  45. };
  46.  
  47. bool valid(ll maxD) {
  48.     ll x = newRow(a[1].first - maxD, a[1].second);
  49.     ll y = newCol(a[1].first, a[1].second - maxD);
  50.     ll u = newRow(a[1].first + maxD, a[1].second);
  51.     ll v = newCol(a[1].first, a[1].second + maxD);
  52.  
  53.     Rect cur(x, y, u, v);
  54.  
  55.     for (int i = 2; i <= n; i++) {
  56.         ll x = newRow(a[i].first - maxD, a[i].second);
  57.         ll y = newCol(a[i].first, a[i].second - maxD);
  58.         ll u = newRow(a[i].first + maxD, a[i].second);
  59.         ll v = newCol(a[i].first, a[i].second + maxD);
  60.         cur = cur.intersect(Rect(x, y, u, v));
  61.         if (cur == Rect().empty()) return false;
  62.     };
  63.  
  64.     if (cur.x == cur.u && cur.y == cur.v) {
  65.         return ((cur.x & 1) == (cur.y & 1));
  66.     };
  67.  
  68.     return true;
  69. };
  70.  
  71. int main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0);
  74.     if (fopen("D5MPOINT.INP", "r")) {
  75.         freopen("D5MPOINT.INP", "r", stdin);
  76.         freopen("D5MPOINT.OUT", "w", stdout);
  77.     };
  78.  
  79.     cin >> n;
  80.     for (int i = 1; i <= n; i++) {
  81.         cin >> a[i].first >> a[i].second;
  82.     };
  83.  
  84.     ll l = 0, r = 8e18, res = 8e18;
  85.     while (l <= r) {
  86.         ll mid = (l + r) >> 1;
  87.         if (valid(mid)) {
  88.             res = mid;
  89.             r = mid - 1;
  90.         } else
  91.             l = mid + 1;
  92.     };
  93.  
  94.     cout << res << '\n';
  95. };
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/iwetya
language:
C++14 (gcc 8.3)
created:
8 hours 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!