Guest User

1419F

a guest
Sep 19th, 2020
1,629
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb emplace_back
  6. #define fi first
  7. #define se second
  8. #define all(x) (x).begin(), (x).end()
  9. #define ll long long
  10. #define pii pair<int, int>
  11.  
  12. const int INF = 2e9 + 1;
  13.  
  14. vector<vector<int>> g;
  15. vector<int> usd;
  16.  
  17. void dfs(int v, int col) {
  18.     usd[v] = col;
  19.     for (auto &to : g[v]) {
  20.         if (!usd[to]) dfs(to, col);
  21.     }
  22. }
  23.  
  24. int main(){
  25.     cin.tie(0);
  26.     cout.tie(0);
  27.     ios_base::sync_with_stdio(0);
  28.     int n;
  29.     cin >> n;
  30.     vector<int> x(n), y(n);
  31.     for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
  32.     map<int, vector<pii>> same_x, same_y;
  33.     for (int i = 0; i < n; i++) {
  34.         same_x[x[i]].pb(y[i], i);
  35.         same_y[y[i]].pb(x[i], i);
  36.     }
  37.     for (auto &c : same_x) sort(all(c.se));
  38.     for (auto &c : same_y) sort(all(c.se));
  39.     ll left = -1, right = INF;
  40.     while (right - left > 1) {
  41.         ll mid = (left + right) / 2;
  42.         g.clear();
  43.         g.resize(n);
  44.         for (auto &c : same_x) {
  45.             for (int i = 1; i < (int)c.se.size(); i++) {
  46.                 if (c.se[i].fi - c.se[i - 1].fi <= mid) {
  47.                     g[c.se[i].se].pb(c.se[i - 1].se);
  48.                     g[c.se[i - 1].se].pb(c.se[i].se);
  49.                 }
  50.             }
  51.         }
  52.         for (auto &c : same_y) {
  53.             for (int i = 1; i < (int)c.se.size(); i++) {
  54.                 if (c.se[i].fi - c.se[i - 1].fi <= mid) {
  55.                     g[c.se[i].se].pb(c.se[i - 1].se);
  56.                     g[c.se[i - 1].se].pb(c.se[i].se);
  57.                 }
  58.             }
  59.         }
  60.         int cur = 1;
  61.         usd.assign(n, 0);
  62.         for (int i = 0; i < n; i++) {
  63.             if (usd[i]) continue;
  64.             dfs(i, cur);
  65.             cur++;
  66.         }
  67.         cur--;
  68.         if (cur > 4) {
  69.             left = mid;
  70.             continue;
  71.         }
  72.         bool ok = false;
  73.         if (cur == 1) {
  74.             ok = true;
  75.         } else if (cur == 2) {
  76.             for (int i = 0; i < n; i++) {
  77.                 for (int j = i + 1; j < n; j++) {
  78.                     if (usd[i] == usd[j]) continue;
  79.                     if (x[i] == x[j] && abs(y[i] - y[j]) <= 2 * mid) ok = true;
  80.                     if (y[i] == y[j] && abs(x[i] - x[j]) <= 2 * mid) ok = true;
  81.                     if (abs(x[i] - x[j]) <= mid && abs(y[i] - y[j]) <= mid) ok = true;
  82.                 }
  83.             }
  84.         } else if (cur == 3) {
  85.             vector<pii> seg;
  86.             for (auto &c : same_x) {
  87.                 for (int i = 1; i < (int)c.se.size(); i++) {
  88.                     if (usd[c.se[i].se] != usd[c.se[i - 1].se]) {
  89.                         seg.pb(c.se[i].se, c.se[i - 1].se);
  90.                     }
  91.                 }
  92.             }
  93.             for (auto &c : same_y) {
  94.                 for (int i = 1; i < (int)c.se.size(); i++) {
  95.                     if (usd[c.se[i].se] != usd[c.se[i - 1].se]) {
  96.                         seg.pb(c.se[i].se, c.se[i - 1].se);
  97.                     }
  98.                 }
  99.             }
  100.             for (auto &c : seg) {
  101.                 int i = c.fi, j = c.se;
  102.                 for (int k = 0; k < n; k++) {
  103.                     if (usd[k] == usd[i] || usd[k] == usd[j]) continue;
  104.                     if (x[i] == x[j]) {
  105.                         if (min(y[i], y[j]) >= y[k] || max(y[i], y[j]) <= y[k]) continue;
  106.                         if (abs(x[i] - x[k]) > mid) continue;
  107.                         if (abs(y[i] - y[k]) <= mid && abs(y[j] - y[k]) <= mid) ok = true;
  108.                     } else {
  109.                         if (min(x[i], x[j]) >= x[k] || max(x[i], x[j]) <= x[k]) continue;
  110.                         if (abs(y[i] - y[k]) > mid) continue;
  111.                         if (abs(x[i] - x[k]) <= mid && abs(x[j] - x[k]) <= mid) ok = true;
  112.                     }
  113.                 }
  114.             }
  115.         } else {
  116.             vector<pii> segx, segy;
  117.             for (auto &c : same_x) {
  118.                 for (int i = 1; i < (int)c.se.size(); i++) {
  119.                     if (usd[c.se[i].se] != usd[c.se[i - 1].se]) {
  120.                         segx.pb(c.se[i].se, c.se[i - 1].se);
  121.                     }
  122.                 }
  123.             }
  124.             for (auto &c : same_y) {
  125.                 for (int i = 1; i < (int)c.se.size(); i++) {
  126.                     if (usd[c.se[i].se] != usd[c.se[i - 1].se]) {
  127.                         segy.pb(c.se[i].se, c.se[i - 1].se);
  128.                     }
  129.                 }
  130.             }
  131.             for (auto &c : segx) {
  132.                 for (auto &l : segy) {
  133.                     int i = c.fi, j = c.se, k = l.fi, p = l.se;
  134.                     if (usd[i] == usd[k] || usd[i] == usd[p] || usd[j] == usd[p] || usd[j] == usd[k]) continue;
  135.                     if (min(y[i], y[j]) >= y[k]) continue;
  136.                     if (max(y[i], y[j]) <= y[k]) continue;
  137.                     if (min(x[k], x[p]) >= x[i]) continue;
  138.                     if (max(x[k], x[p]) <= x[i]) continue;
  139.                     int x0 = x[i], y0 = y[k];
  140.                     if (abs(y[i] - y0) <= mid && abs(y[j] - y0) <= mid && abs(x[p] - x0) <= mid && abs(x[k] - x0) <= mid) ok = true;
  141.                 }
  142.             }
  143.         }
  144.         if (ok) right = mid;
  145.         else left = mid;
  146.     }
  147.     cout << (right == INF ? -1 : right);
  148.     return 0;
  149. }
RAW Paste Data