TopCoder SRM 836 : Div1 Easy Div2 Hard IntersectionArea

どれもコーナーケースにやられがちな問題で、幸いEasyとHard通したら割とよい順位になった。
https://community.topcoder.com/stat?c=problem_statement&pm=17795

問題

2次元座標上で、軸に平行な四角形が4つ与えられる。
ここに面積が正の四角形を1つ追加し、全四角形の共通部分の面積をAにしたい。
可能かどうか判定し、可能なら四角形の例を1つ示せ。
ただし、各四角形は(0,0)-(1000000,1000000)の範囲に収まらなければならない。

解法

基本的な方針は簡単で、まず与えられた四角形の共通部分をとる。
そして、Aの約数を求めて共通部分の幅・高さを総当たりし、それが上記共通部分に含まれるならそのような四角形を構成すればよい。
ただしこの問題2つコーナーケースがある。

• 与えられる矩形が0個の場合がある。これを防ぐには、仮に(0,0)-(1000000,1000000)の四角形があると仮定すると良い。
• A=0の場合、共通部分を避けるように四角形を配置する必要がある。共通部分が(0,0)-(1000000,1000000)を覆っているとき、解なしなので注意。

const int V=1000000;
class IntersectionArea {
	public:
	vector <int> addOne(vector <int> X1, vector <int> Y1, vector <int> X2, vector <int> Y2, long long A) {
		int L=0,R=V,T=V,B=0;
		int x,y;
		int N=X1.size();
		int i;
		FOR(i,N) {
			L=max(L,X1[i]);
			R=min(R,X2[i]);
			B=max(B,Y1[i]);
			T=min(T,Y2[i]);
		}
		
		if(A==0) {
			if(L>0||B>0) return {0,0,1,1};
			if(T<V||R<V) return {V-1,V-1,V,V};
		}
		else {
			for(ll w=1;L+w<=R;w++) if(A%w==0) {
				ll h=A/w;
				if(h<=T-B) {
					return {L,B,(int)(L+w),(int)(B+h)};
				}
			}
		}
		return {};
		
	}
}

まとめ

矩形が0個の場合を見落としていたが、幸い共通部分の初期値を(0,0)-(1000000,1000000)にしていたため助かった。