Codeforces #488 Div1 A. Two Squares

今回色々ひどすぎた。
http://codeforces.com/contest/993/problem/A

問題

２次元座標上において、格子点を頂点とする２つの正方形が与えられる。
片方は軸に平行で、もう片方は軸に45度を成す。
両者は共通部分を持つか答えよ。

解法

座標が小さいので実際に両方の占める範囲を塗りつぶすのが手っ取り早い。
点で接する場合の扱いが手間なので、斜めの正方形を上下左右1だけサイズを拡大してしまうとよい。

int AL,AR,AT,AD;
int BL,BR,BT,BD;

int C[302][302];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	AL=101,AR=-101,AT=101,AD=-101;
	BL=101,BR=-101,BT=101,BD=-101;
	FOR(i,4) {
		cin>>x>>y;
		AL=min(AL,x);
		AR=max(AR,x);
		AT=min(AT,y);
		AD=max(AD,y);
	}
	AL+=102;
	AR+=102;
	AT+=102;
	AD+=102;
	
	FOR(i,4) {
		cin>>x>>y;
		BL=min(BL,x);
		BR=max(BR,x);
		BT=min(BT,y);
		BD=max(BD,y);
	}
	BL+=102;
	BR+=102;
	BT+=102;
	BD+=102;
	BL--,BR++;
	BT--;
	BD++;
	
	for(y=AT;y<AD;y++) {
		for(x=AL;x<AR;x++) C[y][x] |= 1;
	}
	
	int w=0;
	for(y=BT;y<BD;y++) {
		int mt=(BD+BT)/2;
		if(y<mt) w++;
		else if(y>mt) w--;
		for(x=(BL+BR)/2-w;x<(BL+BR)/2+w;x++) C[y][x] |= 2;
	}
	FOR(y,300) FOR(x,300) {
		if(C[y][x]==3) return _P("YES\n");
		
	}
	_P("NO\n");
}

まとめ

問題文ちゃんと読んだつもりが、点で接する場合は共通部分を持たないと誤読してWAした。