# USACO Gold 2016 Open - Splitting the Field

Authors: Óscar Garries, Benjamin Qi, Ryan Chou

### Warning: Weak Test Data

Some accepted submissions may give different outputs on the following test case:

The right answer should be $6$.

Code Snippet: Test Case (Click to expand)

## Explanation

Since the enclosures must be rectangular, there *must* be a vertical or horizontal line that separates the two. Otherwise,
we'd have a case where one enclosure would have to overlap the other in order to enclose all the cows.

Thus, we'll perform two sweeps, one checking vertical splits, and the other checking horizontal splits. To keep track of the best answer, we'll keep prefix and suffix minimums and maximums to calculate each possible solution in $\mathcal{O}(1)$ time.

We can also use a binary search tree instead of prefix/suffix minimums and maximums. To do this, we can create two ordered sets: a set representing the current enclosure, and a set representing the other enclosure. As we sweep across these coordinates, we'll add them to the current set and remove them from the other enclosure. To query, we'll fetch the minimum and maximum values from the sets.

## Implementation

**Time Complexity:** $\mathcal{O}(N \log N)$

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;int n;ll ans = 0;vector<pair<int, int>> cows;/** returns the maximum area saved by testing splits along cows[i].first */

Java

import java.io.*;import java.util.*;public class SplittingTheField {// returns updated min/maxs when considering a new coordinatepublic static Pair upd(Pair a, long b) {return new Pair(Math.min(a.first, b), Math.max(a.second, b));}public static void main(String[] args) throws Exception {

Python

with open("split.in") as read:n = int(read.readline())cows = [list(map(int, read.readline().split())) for _ in range(n)]ans = 0def search():"""returns the maximum area saved by testing splits along cows[i].first

### 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!