MemSQL start[c]up Round 1 : A. Square and Rectangles

よくわからず参加したけどAしか解けなかった…。
http://codeforces.com/contest/325/problem/A

問題

2次元座標上で、辺が軸に平行なN個の長方形が与えられる。
N個の長方形を全部集めて、中に隙間のない大きな長方形を作れるか答えよ。

解法

N個の長方形があると、最大2N個のX座標とY座標があり得る。
そこで、これらの座標から構築できる2N*2N個の長方形が、元のN個の長方形のいずれかに含まれるかを調べればよい。

…ただ、後で知ったけどX座標の最大値最小値およびY座標の最大値最小値から得られる長方形の面積と、元のN個の面積の和を比較した方が楽だったっぽい。

int N;
vector<pair<int,int> > V;
vector<int> XX,YY;

void uniq(vector<int>& DD) {
	vector<int> VV=DD;
	sort(VV.begin(),VV.end());
	VV.erase(unique(VV.begin(),VV.end()),VV.end());
	int i,j,k;
	FOR(i,DD.size()) {
		k=DD[i];
		FOR(j,VV.size()) if(k==VV[j]) DD[i]=j+1;
	}
}

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y>>j>>k;
		XX.push_back(x);
		YY.push_back(y);
		XX.push_back(j);
		YY.push_back(k);
	}
	int lx=*min_element(XX.begin(),XX.end());
	int ly=*min_element(YY.begin(),YY.end());
	int rx=*max_element(XX.begin(),XX.end());
	int ry=*max_element(YY.begin(),YY.end());
	
	if(rx-lx!=ry-ly) return (void)_P("NO\n");
	
	uniq(XX);
	uniq(YY);
	
	lx=*min_element(XX.begin(),XX.end());
	ly=*min_element(YY.begin(),YY.end());
	rx=*max_element(XX.begin(),XX.end());
	ry=*max_element(YY.begin(),YY.end());
	
	for(y=ly;y<ry;y++) {
		for(x=lx;x<rx;x++) {
			int jj=0;
			FOR(i,N) {
				if(XX[i*2]<=x && x<XX[i*2+1] && YY[i*2]<=y && y<YY[i*2+1]) jj=1;
			}
			if(jj==0) return (void)_P("NO\n");
		}
	}
	
	_P("YES\n");
	
	
	return;
}

まとめ

面積か…もっと楽にミスなく書ける方法を考える癖をつけないとね。