(Analysis by Nick Wu)

The warning in the problem statement hints that naively trying to remove every cow and directly evaluating the area of the resulting fence may be too slow.

Consider the fence with the original configuration of cows. If we remove a cow that is not on the fence itself, then the fence will not change. The only time when the fence could change is if we remove a cow that is on the fence itself.

Let us consider the bottom section of the fence. If there is exactly one cow on that section, and we remove it, the bottom section of the fence will shift up to the cow that has the second-smallest y-coordinate. If there are at least two cows on that section though, then the fence will not change.

By similar logic, this is true for each part of the fence. Therefore, it suffices to keep track of the two smallest and two largest x and y coordinates.

Here is my Java code.

import java.io.*;
import java.util.*;
public class reduceB {
// x1 and x2 are the smallest x-coordinates seen
// x3 and x4 are the largest x-coordinates seen
static int x1, x2, x3, x4;
// y1 and y2 are the smallest y-coordinates seen
// y3 and y4 are the largest y-coordinates seen
static int y1, y2, y3, y4;

public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("reduce.out")));
x1 = Integer.MAX_VALUE;
x2 = Integer.MAX_VALUE;
x3 = 0;
x4 = 0;
y1 = Integer.MAX_VALUE;
y2 = Integer.MAX_VALUE;
y3 = 0;
y4 = 0;
int[] x = new int[n];
int[] y = new int[n];
// read in all the locations
for(int i = 0; i < n; i++) {
x[i] = Integer.parseInt(st.nextToken());
y[i] = Integer.parseInt(st.nextToken());
update(x[i], y[i]);
}
// the original fence has this area
int ans = (x4-x1) * (y4-y1);
for(int i = 0; i < n; i++) {
// check for each point if we use the smallest/largest coordinate
// or the second-smallest/second-largest coordinate
int xMin = x1;
if(x[i] == xMin) {
xMin = x2;
}
int xMax = x4;
if(x[i] == xMax) {
xMax = x3;
}
int yMin = y1;
if(y[i] == yMin) {
yMin = y2;
}
int yMax = y4;
if(y[i] == yMax) {
yMax = y3;
}
// check if the new area is smaller
ans = Math.min(ans, (xMax - xMin) * (yMax - yMin));
}
pw.println(ans);
pw.close();
}

// This function takes in a point and updates the
// two smallest and two largest x and y coordinates.
public static void update(int x, int y) {
if(x < x1) {
x2 = x1;
x1 = x;
}
else if(x < x2) {
x2 = x;
}
if(x > x4) {
x3 = x4;
x4 = x;
}
else if(x > x3) {
x3 = x;
}

if(y < y1) {
y2 = y1;
y1 = y;
}
else if(y < y2) {
y2 = y;
}
if(y > y4) {
y3 = y4;
y4 = y;
}
else if(y > y3) {
y3 = y;
}
}
}