【BZOJ 4581】【Usaco2016 Open】Field Reduction

http://www.lydsy.com/JudgeOnline/problem.php?id=4581

考虑\(O(n^3)\)暴力。

实际上枚举最靠边的三个点就可以了，最多有12个点。

还是暴力= =

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 50003;

int x[N], y[N], id[N], n, minx, maxx, miny, maxy, ansminx, ansmaxx, ansminy, ansmaxy, a[N], tot = 0;

bool cmpx(int X, int Y) {return x[X] < x[Y];}

bool cmpy(int X, int Y) {return y[X] < y[Y];}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)

		scanf("%d%d", x + i, y + i);

	for (int i = 1; i <= n; ++i) id[i] = i;

	minx = miny = 0x7fffffff; maxx = maxy = -0x7fffffff;

	stable_sort(id + 1, id + n + 1, cmpx);

	minx = min(minx, x[id[4]]);

	maxx = max(maxx, x[id[n - 3]]);

	for (int i = 0; i < 3; ++i) {

		a[++tot] = id[1 + i];

		a[++tot] = id[n - i];

	}

	stable_sort(id + 1, id + n + 1, cmpy);

	miny = min(miny, y[id[4]]);

	maxy = max(maxy, y[id[n - 3]]);

	for (int i = 0; i < 3; ++i) {

		a[++tot] = id[1 + i];

		a[++tot] = id[n - i];

	}

	stable_sort(a + 1, a + tot + 1);

	tot = unique(a + 1, a + tot + 1) - a;

	ll ans = -1;

	for (int i = 1; i < tot; ++i)

		for (int j = i + 1; j < tot; ++j)

			for (int k = j + 1; k < tot; ++k) {

				ansminx = minx;

				ansmaxx = maxx;

				ansminy = miny;

				ansmaxy = maxy;

				for (int tmp = 1; tmp < tot; ++tmp)

					if (tmp != i && tmp != j && tmp != k) {

						ansminx = min(ansminx, x[a[tmp]]);

						ansmaxx = max(ansmaxx, x[a[tmp]]);

						ansminy = min(ansminy, y[a[tmp]]);

						ansmaxy = max(ansmaxy, y[a[tmp]]);

					}

				if ((ansminx >= ansmaxx) || (ansminy >= ansmaxy))

					ans = 0;

				else

					if (ans == -1)

						ans = 1ll * (ansmaxx - ansminx) * (ansmaxy - ansminy);

					else

						ans = min(ans, 1ll * (ansmaxx - ansminx) * (ansmaxy - ansminy));

			}

	printf("%lld\n", ans);

	return 0;

}