Skip to Content

Splitting the Field

Análisis oficial (Java) 

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 O(1)\mathcal{O}(1) 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: O(NlogN)\mathcal{O}(N \log N)

#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); } } // EndCodeSnip
with 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"))