forked from: flash on 2010-5-15

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

// forked from uwi's flash on 2010-5-15
package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    // @see http://projecteuler.net/index.php?section=problems&id=
    public class Euler extends Sprite {
        private var _tf : TextField;
  
        public function Euler() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(60));
            tr(ct);
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private var _n : uint;
        private var _vecs : Array;
        
        private var _map : Object;

        private function solve(n : uint) : Number
        {
        		_n = (n - 1) / 2;
        		_vecs = [];
        		for(var i : uint = 1;i <= _n;i++){
        			_vecs.push({x:i, y:0, l:i});
        			_vecs.push({x:0, y:i, l:i});
        			_vecs.push({x:-i, y:0, l:i});
        			_vecs.push({x:0, y:-i, l:i});
        		}
        		countFractions(0, 1, 1, 1);
        		tr("len : " + _vecs.length);
        		
        		var v : Object;
        		for each(v in _vecs){
        			v.a = Math.atan2(v.y, v.x);
//        			tr(v.x, v.y, v.l, v.a);
        		}
        		_vecs.sortOn("a", Array.NUMERIC);
//        		return 0; 
        		
        		
        		var ret : Number = 0;
        		for(var u : uint = 0;u < _vecs.length && _vecs[u].a < -EPS;u++){
	        		_map = {};
	        		_map[enc(_vecs[u].x, _vecs[u].y, u, _vecs[u].l)] = 1;
	        		var sa : Number = _vecs[u].a + Math.PI;
        		for(var p : uint = 2;;p++){
        			var mct : uint = 0;
	        		var nmap : Object = {};
        			for(var key : String in _map){
        				var pxyl : Array = dec(Number(key));
        				var pos : uint = pxyl[0];
        				var x : int = pxyl[1];
        				var y : int = pxyl[2];
        				var len : int = pxyl[3];
	        			if(x == 0 && y == 0){
	        				if(p >= 3 && _vecs[pos].a > sa + EPS){
	        					ret += _map[key];
	        				}
	        				continue;
	        			}
		        		for(i = pos + 1;i < _vecs.length && x * _vecs[i].y - y * _vecs[i].x > -EPS;i++){
		        			ct++;
		        			if(_vecs[i].a - _vecs[pos].a > EPS && 
		        				len + _vecs[i].l + Math.sqrt((x + _vecs[i].x) * (x + _vecs[i].x) + (y + _vecs[i].y) * (y + _vecs[i].y)) <= n + EPS){
//        				tr(p, x, y, pos, len, _vecs[i].x, _vecs[i].y, _vecs[i].a, sa);
		        				var code : uint = enc(x + _vecs[i].x, y + _vecs[i].y, i, len + _vecs[i].l);
		        				if(!nmap[code])nmap[code] = 0;
//        				tr(p, x, y, pos, len);
		        				nmap[code] += _map[key];
		        				mct++;
		        			}
		        		}
        			} 
	        		if(mct == 0)break;
//	        		tr("mct", p, mct);
        			_map = nmap;
        		}
        		}
        		return ret;
//        		return countFractions(0, 1, 1, 1);
        }
        
        private var EPS : Number = 0.000001;
        private var ct : uint = 0;
        
        private function enc(x : int, y : int, pos : int, len : int) : Number
        {
        		return ((pos * 120 + (x + 60)) * 120 + (y + 60)) * 120 + len;
        }
        
        private function dec(k : uint) : Array
        {
        		var len : int = k % 120;k /= 120;
        		var y : int = (k % 120) - 60;k /= 120;
        		var x : int = (k % 120) - 60;k /= 120;
        		return [k, x, y, len];
        }
        
        private function rec(pos : int, x : int, y : int, len : int, sa : Number) : Number
        {
        		if(x == 0 && y == 0){
        			return _vecs[pos].a > sa + EPS ? 1 : 0;
        		}
        		var ret : Number = 0;
        		for(var i : uint = pos + 1;i < _vecs.length && x * _vecs[i].y - y * _vecs[i].x > -EPS;i++){
        			ct++;
        			if(_vecs[i].a - _vecs[pos].a > EPS && 
        				_vecs[i].l + Math.sqrt((x + _vecs[i].x) * (x + _vecs[i].x) + (y + _vecs[i].y) * (y + _vecs[i].y)) <= len + EPS){
        				ret += rec(i, x + _vecs[i].x, y + _vecs[i].y, len - _vecs[i].l, sa);
        			}
        		}
        		return ret;
        }

        private function countFractions(sn : int, sd : int, en : int, ed : int) : Number
        {
			var hn : int = sn;
			var hd : int = sd;
			var seg : Array = [en, ed];
        		var ret : Number = 0; 
        		while(seg.length >= 2){
        			var nn : int = hn + seg[0];
        			var nd : int = hd + seg[1];
        			var c : Number = count(nn, nd);
        			if(c != -1){
        				ret += c;
        				seg.unshift(nn, nd);
        			}else{
        				hn = seg.shift();
        				hd = seg.shift();
        			}
        		}
        		return ret;
        }
        
        private function count(n : uint, d : uint) : Number
        {
        		if(((d ^ n) & 1) == 0)return 0;
        		var M : uint = d * d - n * n;
        		var N : uint = 2 * n * d;
        		var O : uint = d * d + n * n;
        		for(var p : int = 1;O * p <= _n;p++){
        			_vecs.push({x:M*p, y:N*p, l:O*p});
        			_vecs.push({x:M*p, y:-N*p, l:O*p});
        			_vecs.push({x:-M*p, y:N*p, l:O*p});
        			_vecs.push({x:-M*p, y:-N*p, l:O*p});
        			_vecs.push({x:N*p, y:M*p, l:O*p});
        			_vecs.push({x:N*p, y:-M*p, l:O*p});
        			_vecs.push({x:-N*p, y:M*p, l:O*p});
        			_vecs.push({x:-N*p, y:-M*p, l:O*p});
        			tr(M * p, N * p, O * p);
        		}
        		return p == 1 ? -1 : p - 1;
        } 
        
        private function tr(...o : Array) : void
        {
            _tf.appendText(o + "\n");
            _tf.scrollV = _tf.maxScrollV;
        }
    }
}