(Analysis by Nick Wu)

The critical observation to solving this problem is that there must exist some line, either horizontal or vertical, which separates the two enclosures. Assume without loss of generality that the line is vertical (we can reflect all the point along the line $y=x$). We will do a vertical line sweep across the plane, computing the area needed for an enclosure to the left of the line and to the right of the line. Because the line sweep guarantees the width of the enclosures, we only need to know how to compute the heights. We can store the y-coordinates in a balanced binary search tree, giving us an $O(N \log N)$ algorithm. This is what my Java solution does below. Note that it is also possible to dispense with the binary search trees entirely and just keep running mins and maxes in y.

import java.io.*;
import java.util.*;
public class split {

static long totalArea;

public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("split.out")));
State[] list = new State[n];
for(int i = 0; i < n; i++) {
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
list[i] = new State(x, y);
}
long ans = solve(list);
transpose(list);
ans = Math.min(ans, solve(list));
pw.println(totalArea - ans);
pw.close();
}

public static long solve(State[] list) {
Arrays.sort(list);
TreeMap<Integer, Integer> rhs = new TreeMap<Integer, Integer>();
for(State curr: list) {
update(rhs, curr.y, 1);
}
long ret = totalArea = (list[list.length-1].x - list[0].x) * (long)(rhs.lastKey() - rhs.firstKey());
TreeMap<Integer, Integer> lhs = new TreeMap<Integer, Integer>();
for(int i = 0; list[i].x < list[list.length-1].x;) {
int j = i+1;
while(j < list.length && list[i].x == list[j].x) {
j++;
}
for(int k = i; k < j; k++) {
update(rhs, list[k].y, -1);
update(lhs, list[k].y, 1);
}
ret = Math.min(ret, (list[i].x - list[0].x) * (long)(lhs.lastKey() - lhs.firstKey()) + (list[list.length-1].x - list[j].x) * (long)(rhs.lastKey() - rhs.firstKey()));
i = j;
}
return ret;
}

public static void update(Map<Integer, Integer> m, int k, int v) {
if(!m.containsKey(k)) {
m.put(k, 0);
}
int next = m.get(k) + v;
if(next == 0) {
m.remove(k);
}
else {
m.put(k, next);
}
}

public static void transpose(State[] list) {
for(State curr: list) {
curr.transpose();
}
}

static class State implements Comparable<State> {
public int x,y;
public State(int a, int b) {
x=a;
y=b;
}
public void transpose() {
int t = x;
x = y;
y = t;
}
public int compareTo(State s) {
return x - s.x;
}
}

}