Official Analysis (C++)

Explanation

To start, consider the problem without removing three cows. The minimum area of the enclosing fence is the product of the difference between the largest x-coordinate and smallest x-coordinate and the difference between the largest y-coordinate and smallest y-coordinate.

To reduce this bounding box, we must remove the cows near the four boundaries of the rectangle. Since we can only remove at most three cows, we should only consider the three extremes on each direction. That means our candidates include the three cows with the smallest x-values, the three with the largest x-values, the three with the smallest y-values, and the three with the largest y-values. This candidate set thus includes no more than twelve cows. Finally, we can simply brute force removing all combinations of three candidates and find the minimum enclosing rectangle of the new set of coordinates.

Note that removing less than three cows is not beneficial, as removing one more cow will either decrease the area or make it stay the same.

Implementation

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

Copy
import itertools

with open("reduce.in") as read:
	n = int(read.readline())
	coordinates = [tuple(map(int, read.readline().split())) for i in range(n)]

sort_by_x = sorted(coordinates)
sort_by_y = sorted(coordinates, key=lambda coord: coord[1])
candidates = sort_by_x[:3] + sort_by_x[-3:] + sort_by_y[:3] + sort_by_y[-3:]
min_area = float("inf")