TopCoder SRM 500 Div1 Medium: FractalPicture

解法

500回フラクタルを成長させるが、長方形の各頂点は格子点なので、6回め以降に生成された線分についてはまとめて考えることができる。

コード

import java.util.ArrayDeque;
import java.util.ArrayList;

public class FractalPicture {

	public double getLength(int x1, int y1, int x2, int y2) {
		// 新しい線の形成に関わる線分を保存しておく
		ArrayDeque<FracLine> lines = new ArrayDeque<>();
		lines.add(new FracLine(0, 0, 0, 81));

		// 今後新しい線分の形成に関わらない線分を保存しておく
		ArrayList<FracLine> finalLines = new ArrayList<>();

		// 長さ1の線分が形成されるまでフラクタルを成長させる
		for (int i = 0; i < 4; i++) {
			int size = lines.size();
			for (int j = 0; j < size; j++) {
				FracLine line = lines.poll();
				int length = line.length();
				int fromx = (line.to.x - line.from.x) / 3 * 2 + line.from.x;
				int fromy = (line.to.y - line.from.y) / 3 * 2 + line.from.y;
				int tox = line.to.x;
				int toy = line.to.y;
				lines.add(new FracLine(fromx, fromy, tox, toy));
				if (fromx == tox) {
					int rx = fromx + length / 3;
					int lx = fromx - length / 3;
					lines.add(new FracLine(fromx, fromy, rx, fromy));
					lines.add(new FracLine(fromx, fromy, lx, fromy));
				} else {
					int uy = fromy + length / 3;
					int dy = fromy - length / 3;
					lines.add(new FracLine(fromx, fromy, fromx, uy));
					lines.add(new FracLine(fromx, fromy, fromx, dy));
				}
				finalLines.add(new FracLine(line.from.x, line.from.y, fromx,
						fromy));
			}
		}

		double ans = 0;

		// 長さ1の線分からフラクタルが成長していく場合、1ステップで片側につき1/3ずつ線分が増えていくので
		// 残りの495ステップで495*2/3だけ増える
		while (!lines.isEmpty()) {
			FracLine line = lines.poll();
			if (!line.isIncluded(x1, y1, x2, y2)) {
				continue;
			}
			// 長さ1の線分が長方形に含まれる場合
			ans += 1.0;

			if (line.onBorder(x1, y1, x2, y2)) {
				// 線分が長方形の境界上にある場合
				ans += 495 / 3;
			} else {
				ans += 495 * 2 / 3;
			}
		}

		// 長さが1より大きい線分について計算する
		for (FracLine l : finalLines) {
			if (l.from.x == l.to.x && x1 <= l.from.x && l.from.x <= x2) {
				int min = Math.max(y1, Math.min(l.from.y, l.to.y));
				int max = Math.min(y2, Math.max(l.from.y, l.to.y));
				if (max - min < 0) {
					continue;
				}
				ans += (max - min);
			}
			if (l.from.y == l.to.y && y1 <= l.from.y && l.from.y <= y2) {
				int min = Math.max(x1, Math.min(l.from.x, l.to.x));
				int max = Math.min(x2, Math.max(l.from.x, l.to.x));
				if (max - min < 0) {
					continue;
				}
				ans += (max - min);
			}
		}

		return ans;
	}
}

class FracLine {
	Vector2D from, to;

	public FracLine(int fromx, int fromy, int tox, int toy) {
		this.from = new Vector2D(fromx, fromy);
		this.to = new Vector2D(tox, toy);
	}

	public int length() {
		int dx = from.x - to.x;
		int dy = from.y - to.y;
		return (int) Math.sqrt(dx * dx + dy * dy);
	}

	public boolean isIncluded(int x1, int y1, int x2, int y2) {
		boolean fromIn = x1 <= from.x && from.x <= x2 && y1 <= from.y
				&& from.y <= y2;
		boolean toIn = x1 <= to.x && to.x <= x2 && y1 <= to.y && to.y <= y2;
		return fromIn && toIn;
	}

	public boolean onBorder(int x1, int y1, int x2, int y2) {
		if (from.x == to.x && (from.x == x1 || from.x == x2)) {
			return true;
		}
		if (from.y == to.y && (from.y == y1 || from.y == y2)) {
			return true;
		}
		return false;
	}
}

class Vector2D {
	int x;
	int y;

	public Vector2D(int x, int y) {
		this.x = x;
		this.y = y;
	}
}