Splitting the Field

USACO 2016 US Open - Gold, Problem 1

Algorithm

Finding the area required for one fence is trivial (just find the topmost, leftmost, rightmost and bottommost cows).

Notice that to have two non-overlapping fences, there has to be a vertical or horizontal line that separates the two fences. Without loss of generality assume that the optimal dividing line is vertical. We can then scan from left to right, calculating how much area is needed for the two fences.

For the left fence:

the left edge is the x-coordinate of the leftmost cow
the right edge is the x-coordinate of the cow closest but left of the dividing line
to find the top edge, we can keep a running maximum of the y-coordinates of each cow (since the y-coordinate of the topmost point will only ever increase as we scan)
to find the bottom edge, we keep a running minimum of the y-coordinates of each cow

We use a similar method to find the dimensions of the right fence. To solve for horizontal dividing lines, we can reflect the points across the line y=x.

Python

f_in = open("split.in", "r")
f_out = open("split.out", "w")

input = f_in.readline
print = f_out.write

# Get cow positions
n = int(input())
cows = []
for i in range(n):
    cows.append(list(map(int, input().split())))

# Get area
def run_single(cows):
    # gets area required for single fence
    min_x = min(cows, key=lambda i:i[0])[0]
    max_x = max(cows, key=lambda i:i[0])[0]
    min_y = min(cows, key=lambda i:i[1])[1]
    max_y = max(cows, key=lambda i:i[1])[1]

    area = (max_x - min_x) * (max_y - min_y)
    #print("single area",area)
    return area

def run_double(cows):
    # gets area required for two fences, with
    # vertical dividing line
    cows.sort(key=lambda i:i[0]) # sort in ascending order of x pos
    min_x = cows[0][0]
    max_x = cows[-1][0]

    # store each unique x position as well as the last
    # position in cows where that x is found
    # [x, last_cow_index, max_y, min_y]
    columns = []
    for i, cow in enumerate(cows):
        if i==0 or cow[0] != columns[-1][0]:
            columns.append([cow[0], i, cow[1], cow[1]])
        else:
            columns[-1][1] = i
            columns[-1][2] = max(columns[-1][2], cow[1])
            columns[-1][3] = min(columns[-1][3], cow[1])

    # build prefix-sum like arrays to store max/min y vals
    left_y_prefixes = []
    current_max = 0
    current_min = float("inf")
    for i in range(len(columns)):
        current_max = max(current_max, columns[i][2])
        current_min = min(current_min, columns[i][3])
        left_y_prefixes.append([current_max, current_min])

    right_y_prefixes = []
    current_max = 0
    current_min = float("inf")
    for i in range(len(columns)-1,-1,-1):
        current_max = max(current_max, columns[i][2])
        current_min = min(current_min, columns[i][3])
        right_y_prefixes.append([current_max, current_min])
    right_y_prefixes = right_y_prefixes[::-1]

    # print(left_y_prefixes,right_y_prefixes)

    min_total_area = float("inf")
    num_columns = len(columns)
    for i in range(len(columns)-1):
        x = columns[i][0]
        next_x = columns[i+1][0]

        min_y_left = left_y_prefixes[i][1]
        max_y_left = left_y_prefixes[i][0]
        area_left = (x-min_x)*(max_y_left-min_y_left)

        min_y_right = right_y_prefixes[i+1][1]
        max_y_right = right_y_prefixes[i+1][0]
        area_right = (max_x-next_x)*(max_y_right-min_y_right)

        #print(area_left,area_right)
        min_total_area = min(min_total_area, area_left+area_right)
    #print("double area", min_total_area)
    return min_total_area

# Main
def main():
    single_area = run_single(cows)
    double_area_vertical = run_double(cows)
    cows_reflect = [[c[1], c[0]] for c in cows] # reflect across y=x
    double_area_horizontal = run_double(cows_reflect)
    double_area = min(double_area_horizontal, double_area_vertical)
    print(str(single_area-double_area)+"\n")

main()