Project Euler 163

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

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

		// 図形は6種類の傾きの直線からなっているので、
		// このうち3種類を選んで、ずらしていって、
		// それぞれの交点が一致せず、かつどれも図形の外になければ
		// 三角形としてカウントする。
		// ループは高々(2*N-1)^3*6^3回
		private function solve(N : uint) : Number
		{
			var a : Array = [
				[f1, 0, N-1], 
				[f2, 0, N-1], 
				[f3, 1, 2*N - 1],
				[f4, 1, 2*N - 1],
				[f5, -N+1, N-1],
				[f6, 1, N]
				];
			var ct : uint = 0;
			for(var i : uint = 0;i < 6;i++){
				for(var j : uint = i + 1;j < 6;j++){
					for(var k : uint = j + 1;k < 6;k++){
						for(var l : int = a[i][1];l <= a[i][2];l++){
							var c1 : Array = a[i][0](l);
							for(var m : int = a[j][1];m <= a[j][2];m++){
								var c2 : Array = a[j][0](m);
								var p12 : Array = cross(c1, c2);
								if(p12[0] < 0 || p12[1] < 0 || p12[0] + p12[1] > 2*N)continue;
								for(var n : int = a[k][1];n <= a[k][2];n++){
									var c3 : Array = a[k][0](n);
									var p23 : Array = cross(c2, c3);
									var p31 : Array = cross(c3, c1);
									if(p23[0] < 0 || p23[1] < 0 || p23[0] + p23[1] > 2*N)continue;
									if(p31[0] < 0 || p31[1] < 0 || p31[0] + p31[1] > 2*N)continue;
									if(Math.abs(p12[0] - p23[0]) < EPS && 
										Math.abs(p23[0] - p31[0]) < EPS
										)continue;
									ct++;
								}
							}
						}
					}
				}
			}
			return ct;
		}
		
		private const EPS : Number = 1E-7;
		
		private function cross(a : Array, b : Array) : Array
		{
			var det : int = -a[2]*b[3]+a[3]*b[2];
			var t : Number = (-b[3] * (b[0] - a[0]) + b[2] * (b[1] - a[1])) / det;
//			var u : Number = (-a[3] * (b[0] - a[0]) + a[2] * (b[1] - a[1])) / det;
			return [a[0] + t * a[2], a[1] + t * a[3]];
		}
		
		// [a,b,c,d]
		// (a+ct)x+(b+dt)y
		private function f1(D : int) : Array { return [2*D, 0, 0, 1];}
		private function f2(D : int) : Array { return [0, 2*D, 1, 0];}
		private function f3(D : int) : Array { return [0, 2*D, D, -2*D];}
		private function f4(D : int) : Array { return [2*D, 0, -2*D, D];}
		private function f5(D : int) : Array { return [2*D, 0, 1, 1];}
		private function f6(D : int) : Array { return [2*D, 0, 1, -1];}
		

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