fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define f1(i, n) for(int i=1;i<=n;++i)
  4. #define f0(i, n) for(int i=0;i<n;i++)
  5. #define all(x) x.begin(), x.end()
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define endl "\n"
  10. #define NAME ""
  11. using namespace std;
  12.  
  13. const int N = 3e5 + 5;
  14.  
  15. int n;
  16. struct point {
  17.     int x, y;
  18. };
  19.  
  20. vector<point> edge;
  21. vector<int> Distance, par;
  22.  
  23. void init(int sz) {
  24.     par.resize(sz + 1);
  25.     for (int i = 1; i <= sz; ++i) par[i] = i;
  26. }
  27.  
  28. int acs(int u) {
  29.     if (u == par[u]) return u;
  30.     return par[u] = acs(par[u]);
  31. }
  32.  
  33. void join(int u, int v) {
  34.     int x = acs(u), y = acs(v);
  35.     if (x != y) {
  36.         par[x] = y;
  37.     }
  38. }
  39.  
  40. int dist(point a, point b) {
  41.     return abs(a.x - b.x) + abs(a.y - b.y);
  42. }
  43.  
  44. bool check(int max_dist) {
  45.     init(n);
  46.     vector<int> adj(n + 1, -1);
  47.  
  48.     for (int i = 1; i <= n; ++i) {
  49.         for (int j = i + 1; j <= n; ++j) {
  50.             if (dist(edge[i], edge[j]) > max_dist) {
  51.                 if (acs(i) == acs(j)) return false;
  52.                 if (adj[i] == -1) adj[i] = j;
  53.                 else join(adj[i], j);
  54.                 if (adj[j] == -1) adj[j] = i;
  55.                 else join(adj[j], i);
  56.             }
  57.         }
  58.     }
  59.  
  60.     return true;
  61. }
  62.  
  63. int32_t main() {
  64.     ios::sync_with_stdio(false);
  65.     cin.tie(nullptr);
  66.  
  67.     if (fopen(NAME".INP", "r")) {
  68.         freopen(NAME".INP", "r", stdin);
  69.         freopen(NAME".OUT", "w", stdout);
  70.     }
  71.  
  72.     cin >> n;
  73.  
  74.     edge.resize(n + 1);
  75.     f1(i, n) cin >> edge[i].x;
  76.     f1(i, n) cin >> edge[i].y;
  77.  
  78.     f1(i, n) {
  79.         for (int j = i + 1; j <= n; ++j) {
  80.             Distance.push_back(dist(edge[i], edge[j]));
  81.         }
  82.     }
  83.  
  84.     if (Distance.empty()) {
  85.         cout << 0; return 0;
  86.     }
  87.  
  88.     sort(all(Distance));
  89.     Distance.erase(unique(all(Distance)), Distance.end());
  90.  
  91.     int l = 0, r = Distance.size() - 1;
  92.     int ans = Distance[r];
  93.     while (l <= r) {
  94.         int mid = (l + r) / 2;
  95.         if (check(Distance[mid])) {
  96.             ans = Distance[mid];
  97.             r = mid - 1;
  98.         }
  99.         else l = mid + 1;
  100.     }
  101.  
  102.     cout << ans;
  103.  
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ie63d5
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!