/* http://usaco.org/index.php?page=viewproblem2&cpid=668 (create a free account) USACO 2019 US Open Silver Ques. 3: Fence Planning This code is not for Sololearn, I recommend onlinegdb.com or visual studio code Make a file named paint.in and put in: 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 Output: 10 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include #include #include using namespace std; typedef pair pii; vector cows; int n, m; vector > connects; unordered_set visited; vector coors; vector q; void find_coor(int i){ coors[0] = cows[i].first < coors[0]? cows[i].first:coors[0]; coors[1] = cows[i].first > coors[1]? cows[i].first:coors[1]; coors[2] = cows[i].second < coors[2]? cows[i].second:coors[2]; coors[3] = cows[i].second > coors[3]? cows[i].second:coors[3]; for(int c = 0; c < connects[i].size();c++){ if(visited.find(connects[i][c]) == visited.end()){ q.push_back(connects[i][c]); visited.insert(connects[i][c]); } } if(!q.empty()){ int lq = q.back(); q.pop_back(); find_coor(lq); } } int main(){ ifstream fin("fenceplan.in"); ofstream fout("fenceplan.out"); fin >> n >> m; int x, y; cows.push_back(make_pair(0, 0)); for(int i = 0; i < n; i++){ fin >> x >> y; cows.push_back(make_pair(x, y)); } int a, b; connects.resize(n + 1); // connects[0].push_back(0); for(int i = 0; i < m; i++){ fin >> a >> b; connects[a].push_back(b); connects[b].push_back(a); } int tmp, result = INT_MAX; for(int i = 1; i < n + 1; i++){ if(visited.find(i) == visited.end()){ visited.insert(i); coors = {INT_MAX, 0, INT_MAX, 0}; find_coor(i); tmp = 2 * (coors[1] - coors[0]) + 2*(coors[3] - coors[2]); result = result > tmp? tmp: result; } } fout << result << endl; fout.close(); fin.close(); return 0; }

USACO #25:Fence Planning C++