Project Euler 212

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/hFiD
 */

package {
	import flash.display.Sprite;
	import flash.text.TextField;
	import flash.utils.getTimer;
	// @see http://projecteuler.net/index.php?section=problems&id=212
	public class Euler212 extends Sprite {
		private var _tf : TextField;
  
		public function Euler212() {
			_tf = new TextField();
			_tf.width = 465;
			_tf.height = 465;
			addChild(_tf);
			
			var s : int = getTimer();
			tr(solve(100));
			var g : int = getTimer();
			tr((g - s) + " ms");
		}

		// x座標でソートして、あとはinclusion-exclusion
		private function solve(N : uint) : Number
		{
			var S : Vector.<uint> = new Vector.<uint>();
			S.push(0);
			var i : uint, j : uint, k : uint;
			for(k = 1;k <= 55;k++){
				S.push((100003 - 200003*k + 300007*k*k*k) % 1000000);
			}
			for(k = 56;k <= 6*N;k++){
				S.push((S[k-24] + S[k-55]) % 1000000);
			}
			
			var points : Array = [];
			for(i = 0;i < N;i++){
				points.push({
					x:S[6*i+1]%10000, 
					y:S[6*i+2]%10000, 
					z:S[6*i+3]%10000, 
					dx:1+(S[6*i+4]%399), 
					dy:1+(S[6*i+5]%399),
					dz:1+(S[6*i+6]%399)
				});
			}
			points.sortOn("x", Array.NUMERIC);
			
			var ret : Number = 0;
			for(i = 0;i < N;i++){
				ret += ie(
					points[i].x, points[i].y, points[i].z,
					points[i].x + points[i].dx, points[i].y + points[i].dy, points[i].z + points[i].dz,
					i, points, N);
			}
			return ret;
		}
		
		// inf-supの体積から、i+1番目以降のcuboidとの交わりの体積を引く
		private function ie(
			xinf : int, yinf : int, zinf : int, 
			xsup : int, ysup : int, zsup : int,
			i : uint, points : Array, N : uint
			) : Number
		{
			var ret : Number = (xsup - xinf) * (ysup - yinf) * (zsup - zinf);
			for(var j : uint = i + 1;j < N && xsup > points[j].x;j++){
				if(	yinf < points[j].y + points[j].dy && 
					points[j].y < ysup &&
					zinf < points[j].z + points[j].dz &&
					points[j].z < zsup
					){
						var nxinf : Number = Math.max(xinf, points[j].x);
						var nyinf : Number = Math.max(yinf, points[j].y);
						var nzinf : Number = Math.max(zinf, points[j].z);
						var nxsup : Number = Math.min(xsup, points[j].x+points[j].dx);
						var nysup : Number = Math.min(ysup, points[j].y+points[j].dy);
						var nzsup : Number = Math.min(zsup, points[j].z+points[j].dz);
						ret -= ie(nxinf, nyinf, nzinf, 
							nxsup, nysup, nzsup,
							j, points, N);
				}
			}
			return ret;
		}

		private function tr(...o : Array) : void
		{
			_tf.appendText(o + "\n");
			_tf.scrollV = _tf.maxScrollV;
		}
	}
}