Project Euler 292

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

package {
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.getTimer;
    import flash.events.Event;
    // @see http://projecteuler.net/index.php?section=problems&id=292
    public class Euler292 extends Sprite {
        private var _tf : TextField;
        private var EPS : Number = 0.000001;
        private var ct : uint = 0;
        private var _n : uint;
        private var _vecs : Array;
  
        public function Euler292() {
            _tf = new TextField();
            _tf.width = 465;
            _tf.height = 465;
            addChild(_tf);
            
            var s : int = getTimer();
            tr(solve(60));
            var g : int = getTimer();
            tr((g - s) + " ms");
        }
        
        private function solve(n : uint) : Number
        {
        		var i : uint, j : uint, k : uint;
        	
        		_n = (n - 1) / 2;
        		_vecs = [];
        		for(i = 1;i <= _n;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);
        		}
        		_vecs.sortOn("a", Array.NUMERIC);
        		
        		var xxx : Vector.<uint> = new Vector.<uint>(120 * 60 * 120);
        		for(i = 0;i < xxx.length;i++)xxx[i] = 0;
        		
        		var map : Object;
        		var u : uint = 0;
        		addEventListener(Event.ENTER_FRAME, function(e:Event) : void {
        			tr("u : " + u + "/" + _vecs.length);
	        		map = {};
	        		map[enc(_vecs[u].x, _vecs[u].y, u, _vecs[u].l)] = 1;
	        		xxx[((_vecs[u].x + 60) * 60 + _vecs[u].y) * 120 + _vecs[u].l]++;
	        		for(var p : uint = 2;;p++){
	        			var mct : uint = 0;
		        		var nmap : Object = {};
	        			for(var key : String in map){
	        				var pos : uint = uint(key) >> 20;
	        				var x : int = ((uint(key) >> 13) & 127) - 60;
	        				var y : int = (uint(key) >> 7) & 63;
	        				var len : int = uint(key) & 127;
			        		for(i = pos + 1;i < _vecs.length && x * _vecs[i].y - y * _vecs[i].x >= 0;i++){
			        			ct++;
			        			if(_vecs[i].a - _vecs[pos].a > EPS && 
							(x + _vecs[i].x) * (x + _vecs[i].x) + (y + _vecs[i].y) * (y + _vecs[i].y) <= (n - len - _vecs[i].l) * (n - len - _vecs[i].l)){
//			        				len + _vecs[i].l + Math.sqrt((x + _vecs[i].x) * (x + _vecs[i].x) + (y + _vecs[i].y) * (y + _vecs[i].y)) <= n + EPS){
			        				var code : uint = enc(x + _vecs[i].x, y + _vecs[i].y, i, len + _vecs[i].l);
			        				if(!nmap[code]){
			        					nmap[code] = map[key];
			        				}else{
				        				nmap[code] += map[key];
			        				}
			        				mct++;
					        		xxx[((x + _vecs[i].x + 60) * 60 + y + _vecs[i].y) * 120 + len + _vecs[i].l] += map[key];
			        			}
			        		}
	        			} 
		        		if(mct == 0)break;
	        			map = nmap;
	        		}
	        			
        			u++;
        			if(u == _vecs.length){
		       		xxx[(60*60+0)*120+0] = 0;
		        		var yyy : Vector.<uint> = new Vector.<uint>(120 * 60 * 120);
		        		for(i = 0;i < yyy.length;i++)yyy[i] = 0;
		        		for(i = 0;i < 120;i++){
		        			for(j = 0;j < 60;j++){
		        				for(k = 1;k < 120;k++){
		        					yyy[(i*60+j)*120+k] = yyy[(i*60+j)*120+k-1] + xxx[(i*60+j)*120+k];
		        				}
		        			}
		        		}
		        		
		        		var ret : Number = 0;
		        		for(i = 0;i < 120;i++){
		        			for(j = 0;j < 60;j++){
		        				for(k = 0;k < 120;k++){
		        					if(xxx[(i*60+j)*120+k] > 0){
		        						ret += xxx[(i*60+j)*120+k] * yyy[(i*60+j)*120+n-k];
		        						if(k * k == (i - 60) * (i - 60) + j * j){
		        							ret--;
		        						}
		        					}
		        				}
		        			}
		        		}
		            tr(ct);
		            tr(ret);
		            removeEventListener(Event.ENTER_FRAME, arguments.callee);
        			}
       		});
        		
        		return 0;
        }
        
        private function enc(x : int, y : int, pos : int, len : int) : Number
        {
        		return pos << 20 | (x + 60) << 13 | y << 7 | len;
        }

        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: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;
        }
    }
}