USACO 2019 US Open Contest Silver Division - Fence Planning

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

For each of the connected componenents, track min width, and min height, to find perimeter entire comp needs; min of all comp perimeters is answer.

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g(1e5 + 1);
vector<bool> visited(1e5 + 1);
vector<pair<int, int>> coords(1e5 + 1);
vector<int> component;

void dfs(int node) {
    visited[node] = true;
    component.push_back(node);
    for (int neighbor : g[node]) {
        if (visited[neighbor] == 0) dfs(neighbor);
    }
}

int main() {
    ifstream cin("fenceplan.in");
    ofstream cout("fenceplan.out");

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        coords[i] = {x, y};
    }
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    long long ans = 1e18;

    for (int i = 1; i <= n; i++) {
        component.clear();
        if (!visited[i]) dfs(i);

        long long min_x = 1e9;
        long long max_x = -1e9;
        long long min_y = 1e9;
        long long max_y = -1e9;

        for (int l : component) {
            pair<long long, long long> of = coords[l];
            min_x = min(min_x, of.first);
            max_x = max(max_x, of.first);
            min_y = min(min_y, of.second);
            max_y = max(max_y, of.second);
        }

        if (!component.empty()) {
            long long perimeter = (max_x - min_x) * 2 + (max_y - min_y) * 2;
            ans = min(ans, perimeter);
        }
    }

    cout << ans << '\n';
}