GCJ2012 Round 2 B : Aerobics

問題概要

W*Hのマットがあり、その中にN個の円(半径はそれぞれ決まっている)を詰める。中心がマットの中に入っていればよい。円同士は重なってはならない。そのような円の配置方法をひとつ出力せよ。マットの面積は円の面積の総和の5倍以上であり、答えが必ず存在することは保証されている。

解法

どうせ貪欲に詰めていっても上手くいくことが保証されてるに違いないとあたりをつけてやってみると上手くいく。大きい順にソートしておいた方がよさそうだけど、その際は元の入力順序を失わないように注意する。

acceptされたコード

import std.stdio, std.algorithm, std.typecons, std.math, std.range;

int N;
int W, H;
int[] rs;

alias Tuple!(int, "w", int, "h", int, "x", int, "y") rect;

void init(){
	scanf("%d%d%d", &N, &W, &H);
	rs = new int[N];
	foreach(i; 0..N){
		scanf("%d", &rs[i]);
	}
}

bool canPut(rect rc, int r){
	if(rc.w <= 0 || rc.h <= 0 || rc.x > W || rc.y > H){
		return false;
	}
	int rx = 2*r, ry = 2*r;
	if(rc.x == 0){
		rx -= r;
	}
	if(rc.y == 0){
		ry -= r;
	}
	
	if(rc.x + rx - r > W || rc.y + ry - r > H){
		return false;
	}
	
	if(rc.x + rc.w == W){
		rx -= r;
	}
	if(rc.y + rc.h == H){
		ry -= r;
	}
	return rx <= rc.w && ry <= rc.h;
}

void solve(){
	//writeln(W , ", ", H);
	auto rects = [rect(W, H, 0, 0)];
	int[] xs, ys;
	
	int[] ids;
	foreach(i; 0..N){
		ids ~= i;
	}
	sort!"a[0] > b[0]"(zip(rs, ids));
	foreach(k, r; rs){
		++r;
		int key = -1;
		foreach(i; 0..rects.length){
			if(canPut(rects[i], r)){
				key = i;
				break;
			}
		}
		if(key == -1){
			writeln();
			writeln(r);
			foreach(rc; rects){
				writeln(rc);
			}
		}
		assert(key >= 0);
		//writeln(r, ", ", rects[key]);
		auto rc = rects[key];
		int rx = 2*r, ry = 2*r;
		if(rc.x == 0){
			rx -= r;
		}
		if(rc.y == 0){
			ry -= r;
		}
		xs ~= rc.x + rx - r;
		ys ~= rc.y + ry - r;
		//writeln(xs[$-1], ", ", ys[$-1]);
		if(!(rc.x + rx - r <= W && rc.y + ry - r <= H)){
			writeln("assert:");
			writeln(W, ", ", H);
			writeln(rects[key]);
			writeln(r);
		}
		assert(rc.x + rx - r <= W && rc.y + ry - r <= H);
		int nw = rc.w - rx, nh = rc.h - ry;
		
		rects ~= rect(nw, ry, rc.x+rx, rc.y);
		rects ~= rect(rx, nh, rc.x, rc.y+ry);
		rects ~= rect(nw, nh, rc.x+rx, rc.y+ry);
		
		rects[key] = rect(-(1<<30),-(1<<30),-1,-1);
	}
	
	foreach(i; 0..N){
		if(xs[i] < 0 || xs[i] > W || ys[i] < 0 || ys[i] > H){
			assert(0);
		}
		foreach(j; i+1..N){
			if(abs(xs[i] - xs[j]) <= rs[i] + rs[j] && abs(ys[i] - ys[j]) <= rs[i] + rs[j]){
				writeln("hoge: ", i , ", ", j);
				assert(0);
			}
		}
	}
	
	foreach(i; 0..N){
		foreach(j; 0..N){
			if(ids[j] == i){
				writef("%d %d%c", xs[j], ys[j], i==N-1 ? '\n' : ' ');
			}
		}
	}
}

void main(){
	int T;
	scanf("%d", &T);
	foreach(c; 0..T){
		init;
		writef("Case #%d: ", c+1);
		solve;
	}
}