Splitting the Field
Solución en video
Por David Zhou
Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++ y Java.
Video de YouTube (kNOSUBvMyTQ)
Solución
Explicación
Como los recintos deben ser rectangulares, debe haber una recta vertical u horizontal que separe a los dos. Si no, tendríamos un caso en el que un recinto tendría que superponerse al otro para encerrar a todas las vacas.

Así, haremos dos barridos, uno comprobando particiones verticales y el otro comprobando particiones horizontales. Para llevar la mejor respuesta, usaremos mínimos y máximos de prefijos y sufijos para calcular cada solución posible en tiempo.
También podemos usar un árbol binario de búsqueda en vez de mínimos y máximos de prefijos/sufijos. Para esto, podemos crear dos conjuntos ordenados: un conjunto que representa el recinto actual, y un conjunto que representa el otro recinto. Al barrer estas coordenadas, las agregamos al conjunto actual y las quitamos del otro recinto. Para consultar, obtenemos los valores mínimo y máximo de los conjuntos.
Implementación
Complejidad temporal:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
ll ans = 0;
vector<pair<int, int>> cows;
/** devuelve el área máxima ahorrada al probar particiones a lo largo de cows[i].first */
ll search() {
sort(cows.begin(), cows.end());
vector<pair<int, int>> pref(n), suf(n);
// devuelve los min/max actualizados al considerar una nueva coordenada
auto upd = [](pair<int, int> a, int b) -> pair<int, int> {
return {min(a.first, b), max(a.second, b)};
};
// computamos mínimos y máximos de prefijos/sufijos
pref[0] = {cows[0].second, cows[0].second};
for (int i = 1; i < n; ++i) { pref[i] = upd(pref[i - 1], cows[i].second); }
suf[n - 1] = {cows[n - 1].second, cows[n - 1].second};
for (int i = n - 2; i >= 0; i--) { suf[i] = upd(suf[i + 1], cows[i].second); }
// área inicial con un solo recinto
ll area = (ll)(cows.back().first - cows.front().first) *
(pref.back().second - pref.back().first);
ll best = LLONG_MAX;
for (int i = 0; i < n - 1; i++) {
// si es posible partir
if (cows[i].first != cows[i + 1].first) {
ll first_rect =
(ll)(cows[i].first - cows[0].first) * (pref[i].second - pref[i].first);
ll second_rect = (ll)(cows.back().first - cows[i + 1].first) *
(suf[i + 1].second - suf[i + 1].first);
best = min(best, first_rect + second_rect);
}
}
return area - best;
}
int main() {
freopen("split.in", "r", stdin);
freopen("split.out", "w", stdout);
cin >> n;
cows.resize(n);
for (pair<int, int> &cow : cows) { cin >> cow.first >> cow.second; }
// probamos todas las particiones en el eje x
ans = max(ans, search());
for (pair<int, int> &cow : cows) { swap(cow.first, cow.second); }
// probamos todas las particiones en el eje y
ans = max(ans, search());
cout << ans << endl;
}import java.io.*;
import java.util.*;
public class SplittingTheField {
// devuelve los min/max actualizados al considerar una nueva coordenada
public 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 {
BufferedReader br = new BufferedReader(new FileReader("split.in"));
int n = Integer.parseInt(br.readLine());
Pair[] cows = new Pair[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
cows[i] = new Pair(x, y);
}
br.close();
long ans = 0;
// halla el área máxima ahorrada al probar particiones a lo largo de cows[i].first
for (int t = 0; t < 2; t++) {
Arrays.sort(cows);
Pair[] pref = new Pair[n];
Pair[] suf = new Pair[n];
// computamos mínimos y máximos de prefijos/sufijos
pref[0] = new Pair(cows[0].second, cows[0].second);
for (int i = 1; i < n; i++) { pref[i] = upd(pref[i - 1], cows[i].second); }
suf[n - 1] = new Pair(cows[n - 1].second, cows[n - 1].second);
for (int i = n - 2; i >= 0; i--) {
suf[i] = upd(suf[i + 1], cows[i].second);
}
// área inicial con un solo recinto
long area = (cows[n - 1].first - cows[0].first) *
(pref[n - 1].second - pref[n - 1].first);
long best = Long.MAX_VALUE;
for (int i = 0; i < n - 1; i++) {
// si es posible partir
if (cows[i].first != cows[i + 1].first) {
long first_rect = (cows[i].first - cows[0].first) *
(pref[i].second - pref[i].first);
long second_rect = (cows[n - 1].first - cows[i + 1].first) *
(suf[i + 1].second - suf[i + 1].first);
best = Math.min(best, first_rect + second_rect);
}
}
ans = Math.max(ans, area - best);
// intercambiamos coordenadas para hallar particiones en el eje y en vez del x
for (int i = 0; i < n; i++) {
long temp = cows[i].first;
cows[i].first = cows[i].second;
cows[i].second = temp;
}
}
PrintWriter pw = new PrintWriter("split.out");
pw.println(ans);
pw.close();
}
}
// BeginCodeSnip{Pair}
class Pair implements Comparable<Pair> {
public long first, second;
public Pair(long x, long y) {
first = x;
second = y;
}
public int compareTo(Pair o) {
if (o.first != first) { return (int)(first - o.first); }
return (int)(second - o.second);
}
}
// EndCodeSnipwith open("split.in") as read:
n = int(read.readline())
cows = [list(map(int, read.readline().split())) for _ in range(n)]
ans = 0
def search():
"""
devuelve el área máxima ahorrada al probar particiones a lo largo de cows[i].first
"""
global ans
cows.sort()
upd = lambda x, y: (min(x[0], y), max(x[1], y))
# computamos mínimos y máximos de prefijos/sufijos
pref = [(cows[0][1], cows[0][1])]
for i in range(1, n):
pref.append(upd(pref[-1], cows[i][1]))
suf = [(cows[-1][1], cows[-1][1])]
for i in range(n - 2, -1, -1):
suf.append(upd(suf[-1], cows[i][1]))
suf.reverse()
# área inicial con un solo recinto
area = (cows[-1][0] - cows[0][0]) * (pref[-1][1] - pref[-1][0])
best = float("inf")
for i in range(n - 1):
# si es posible partir
if cows[i][0] != cows[i + 1][0]:
first_rect = (cows[i][0] - cows[0][0]) * (pref[i][1] - pref[i][0])
second_rect = (cows[-1][0] - cows[i + 1][0]) * (
suf[i + 1][1] - suf[i + 1][0]
)
best = min(best, first_rect + second_rect)
return area - best
# probamos todas las particiones en el eje x
ans = max(ans, search())
cows = [(y, x) for x, y in cows]
# probamos todas las particiones en el eje y
ans = max(ans, search())
print(ans, file=open("split.out", "w"))