Skip to Content
CTRL K

Field Reduction

Análisis oficial (C++) 

Explicación

Para empezar, consideremos el problema sin sacar tres vacas. El área mínima de la cerca envolvente es el producto de la diferencia entre la mayor coordenada xx y la menor coordenada xx y la diferencia entre la mayor coordenada yy y la menor coordenada yy.

Para reducir esta caja envolvente (bounding box), hay que sacar las vacas cercanas a los cuatro bordes del rectángulo. Como solo podemos sacar a lo sumo tres vacas, solo debemos considerar los tres extremos en cada dirección. Eso significa que nuestros candidatos incluyen las tres vacas con los menores valores de xx, las tres con los mayores valores de xx, las tres con los menores valores de yy y las tres con los mayores valores de yy. Este conjunto de candidatos incluye entonces no más de doce vacas. Por último, podemos simplemente probar por fuerza bruta todas las combinaciones de tres candidatos y hallar el rectángulo envolvente mínimo del nuevo conjunto de coordenadas.

Nótese que sacar menos de tres vacas no es beneficioso, porque sacar una vaca más o bien disminuye el área o la deja igual.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log N)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<pair<int, int>> cows(n);
 
	vector<int> sort_by_x(n);
	vector<int> sort_by_y(n);
 
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		cows[i] = {x, y};
 
		sort_by_x[i] = x;
		sort_by_y[i] = y;
	}
 
	sort(sort_by_x.begin(), sort_by_x.end());
	sort(sort_by_y.begin(), sort_by_y.end());
 
	vector<int> candidates;
	for (int i = 0; i < n; i++) {
		auto [x, y] = cows[i];
 
		// the 3 most extreme in any of the 4 directions.
		if (x <= sort_by_x[3] || x >= sort_by_x[n - 3] || y <= sort_by_y[2] ||
		    y >= sort_by_y[n - 3]) {
			candidates.push_back(i);
		}
	}
 
	// Generating subsets with bitmasks
	int min_area = INT_MAX;
	for (int i = 0; i < (1 << candidates.size()); i++) {
		set<int> removing;
		for (int b = 0; b < candidates.size(); b++) {
			if (i & (1 << b)) removing.insert(candidates[b]);
		}
		if (removing.size() != 3) continue;
 
		// Compute area
		int min_x = INT_MAX;
		int max_x = INT_MAX;
		int min_y = INT_MAX;
		int max_y = INT_MAX;
		for (int i = 0; i < cows.size(); i++) {
			if (removing.count(i)) continue;
 
			min_x = min(min_x, cows[i].first);
			max_x = max(max_x, cows[i].first);
			min_y = min(min_y, cows[i].second);
			max_y = max(max_y, cows[i].second);
		}
 
		min_area = min(min_area, (max_x - min_x) * (max_y - min_y));
	}
 
	cout << min_area;
}
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")
 
for removed in itertools.combinations(candidates, 3):
	new_coords = [c for c in coordinates if c not in removed]
	x_coords = [coord[0] for coord in new_coords]
	y_coords = [coord[1] for coord in new_coords]
	area = (max(x_coords) - min(x_coords)) * (max(y_coords) - min(y_coords))
	min_area = min(min_area, area)
 
print(min_area, file=open("reduce.out", "w"))
Fundamentos