USACO 1.4.1 – Packing Rectangles

int l, w, a, b, best=10000000;
vector<vector<int> > rect;
set<pair<int, int> > ans;

#define L(i) rect[perm[i]][rotate[i]>0]
#define W(i) rect[perm[i]][1- (rotate[i]>0)]
#define add(a, b) ans.insert(make_pair(min(a, b), max(a, b)))
#define candidate(a, b)  if(a*b <= best){ best = a*b; add(a, b); }

int main() {
	ofstream fout("packrec.out");
	ifstream fin("packrec.in");

	for (int i = 0; i < 4; i++) {
		fin >> l >> w;
		vector<int> rec;
		rec.push_back(l), rec.push_back(w), rect.push_back(rec);
	}

	for (int o = 0; o < 16; o++) {
		int rotate[4] = {o&1 , o&2, o&4, o&8}, perm[4] = {0, 1, 2, 3};
		do {
			a = W(0) + W(1) + W(2) + W(3)			, b = Max4(L(0), L(1), L(2), L(3));
			candidate(a, b);
			a = Max2(W(0) + W(1) + W(2), W(3))		, b = L(3) + Max3(L(0), L(1), L(2));
			candidate(a, b);
			a = W(3) + Max2(W(0) + W(1), W(2))		, b = Max2(L(3), L(2) + Max2(L(0), L(1)));
			candidate(a, b);
			a = W(0) + Max2(W(1), W(2)) + W(3)		, b = Max3(L(0), L(1) + L(2), L(3));
			candidate(a, b);
			a = Max2(W(0), W(1)) + W(2) + W(3)		, b = Max3(L(0) + L(1), L(2), L(3));
			candidate(a, b);
			a = Max2(W(0)+ W(1), W(2)+ W(3))	        , b = Max2(L(0) + L(3), L(1)+ L(2));
			if (a < W(0) + W(2) && b < L(0) + L(2)) a = W(0) + W(2);
			if (a < W(1) + W(3) && b < L(1) + L(3)) a = W(1) + W(3);
			candidate(a, b);
		}while (next_permutation(perm, perm + 4));
	}
	fout << best << endl;
	for(set<pair<int, int> >::iterator it = ans.begin(); it!=ans.end(); it++)
		if(it->first* it->second==best)
			fout << it->first << " " << it->second << endl;

}
Advertisements

One thought on “USACO 1.4.1 – Packing Rectangles

  1. USACO says:

    I would like to recommend the following web site
    http://usacotraining.blogspot.com/2012/05/purpose.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: