fork download
copy 
  1. /// USACO 2019 US Open Contest, Silver - Fence Planning
  2. /// https://u...content-available-to-author-only...o.org/index.php?page=viewproblem2&cpid=944
  3. /// Author: Qwerty
  4. #include<bits/stdc++.h>
  5. #define fi first
  6. #define se second
  7. using namespace std;
  8. const int MAXN = 1e5 + 100;
  9. int n, m;
  10. pair<int, int> c[MAXN];
  11. vector<int> a[MAXN];
  12. int vis[MAXN];
  13. vector<int> comp[MAXN];
  14. int cnt = 1;
  15. void dfs(int u){
  16.     vis[u] = 1;
  17.     comp[cnt].push_back(u);
  18.     for (int v: a[u]){
  19.          if (!vis[v]){
  20.              dfs(v);
  21.          }
  22.     }
  23. }
  24. int main(){
  25.     //freopen("fenceplan.in", "r", stdin);
  26.     //freopen("fenceplan.out", "w", stdout);
  27.     ios_base::sync_with_stdio(0);
  28.     cin.tie(0);
  29.     cin >> n >> m;
  30.     for (int i = 1; i <= n; i++){
  31.          cin >> c[i].fi >> c[i].se;
  32.     }
  33.     for (int i = 1; i <= m; i++){
  34.          int x, y;
  35.          cin >> x >> y;
  36.          a[x].push_back(y);
  37.          a[y].push_back(x);
  38.     }
  39.     for (int i = 1; i <= n; i++){
  40.          if (!vis[i]){
  41.              dfs(i);
  42.              cnt++;
  43.          }
  44.     }
  45.     cnt--;
  46.     int ans = 1e9;
  47.     for (int i = 1; i <= cnt; i++){
  48.          int minx = 1e9;
  49.          int maxx = 0;
  50.          int miny = 1e9;
  51.          int maxy = 0;
  52.          for (int x: comp[i]){
  53.               minx = min(minx, c[x].first);
  54.               maxx = max(maxx, c[x].first);
  55.               miny = min(miny, c[x].second);
  56.               maxy = max(maxy, c[x].second);
  57.          }
  58.          ans = min(ans, 2 * ((maxx - minx) + (maxy - miny)));
  59.     }
  60.     cout << ans << '\n';
  61. }
  62.  
  63.  
Success #stdin #stdout 0.01s 8664KB
comments (?)
stdin
copy 
7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 6
stdout
copy 
10
https://ideone.com/GTNWQ5
language:
C++14 (gcc 8.3)
created:
4 days 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!