読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #395 Div1 B. Timofey and rectangles

Codeforces

何だこの問題…。
http://codeforces.com/contest/763/problem/B

問題

2次元座標上で以下の条件を満たす矩形がいくつか与えられる。

  • 各頂点は格子点であり、辺は軸に平行である。
  • 互いに点や辺で接することはあるが、正の面積を共有部分として持つことはない。
  • 幅・高さは奇数である。

互いに接する矩形同士が同じ色にならないよう、4色で塗り分けよ。

解法

たとえば、各矩形の左下の点の座標に着目し、X座標の偶奇とY座標の偶奇で4通り塗り分ければよい。
幅・高さが奇数の条件より、同じ色の矩形は互いに接することはない。

int N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cout<<"YES"<<endl;
	FOR(i,N) {
		cin>>x>>y>>r>>j;
		
		x=abs(x)%2;
		y=abs(y)%2;
		cout<<x*2+y+1<<endl;
	}
}

まとめ

こっちがAでもよかったのにね。

広告を非表示にする