Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

We can start a recursive search from each cow and find all cows belonging to the same group.

Then, we can calculate the minimal perimeter of a fence enclosing that group by considering each cow's coordinates. The answer is the smallest perimeter of all such fences.

Implementation

Time Complexity: O(N+M)\mathcal{O}(N + M)

C++

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


struct Cow {
	int x, y;
	vector<int> adj;
	bool visited;
};


vector<Cow> cows;

Java

import java.io.*;
import java.util.*;


public class FencePlan {
	static Cow[] cows;
	static List<Integer>[] graph;
	static boolean[] visited;
	static int lowX = Integer.MAX_VALUE;
	static int highX = Integer.MIN_VALUE;
	static int lowY = Integer.MAX_VALUE;

Python

from typing import List
from sys import setrecursionlimit


setrecursionlimit(10**5)




class Cow:
	def __init__(self, x: int, y: int, adj: List[int], visited: bool) -> None:
		self.x = x
		self.y = y

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum