class Array
  def real_intersection(arr2)
    self_sorted = self.sort
    target_sorted = arr2.sort
    intersection= []
    jstart=0
    for i in (0..self_sorted.length-1)
      for j in (jstart..target_sorted.length-1)
        if self_sorted[i] == target_sorted[j]
          jstart = j+1
          intersection[intersection.length] = self_sorted[i]
          break
        end
      end
    end
    return intersection
  end
end

require 'test/unit'

class ArrayIntersectionTests < Test::Unit::TestCase    
  def test_real_array_intersection
    assert_equal [2], [2, 2, 2, 3, 7, 13, 49] & [2, 2, 2, 5, 11, 107]
    assert_equal [2, 2, 2], [2, 2, 2, 3, 7, 13, 49].real_intersection([2, 2, 2, 5, 11, 107])
    assert_equal ['a', 'c'], ['a', 'b', 'a', 'c'] & ['a', 'c', 'a', 'd']
    assert_equal ['a', 'a', 'c'], ['a', 'b', 'a', 'c'].real_intersection(['a', 'c', 'a', 'd'])
  end
end

float[] checkIntersection(float lineAx1,float lineAy1,float lineAx2,float lineAy2,float lineBx1,float lineBy1,float lineBx2,float lineBy2){
  float aM, bM, aB, bB, isX=0, isY=0;
  if((lineAx2-lineAx1)==0){
    isX=lineAx1;
    bM=(lineBy2-lineBy1)/(lineBx2-lineBx1);
    bB=lineBy2-bM*lineBx2;
    isY=bM*isX+bB;
  }
  else if((lineBx2-lineBx1)==0){
    isX=lineBx1;
    aM=(lineAy2-lineAy1)/(lineAx2-lineAx1);
    aB=lineAy2-aM*lineAx2;
    isY=aM*isX+aB;
  }
  else{
    aM=(lineAy2-lineAy1)/(lineAx2-lineAx1);
    bM=(lineBy2-lineBy1)/(lineBx2-lineBx1);
    aB=lineAy2-aM*lineAx2;
    bB=lineBy2-bM*lineBx2;
    isX=max(((bB-aB)/(aM-bM)),0);
    isY=aM*isX+aB;
  }
  float[] r={
    isX,isY  };
  return r; 
}

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/math/dot-line-length [v1.0]

dotLineLength = function( x, y, x0, y0, x1, y1, o ){
	function lineLength( x, y, x0, y0 ){
		return Math.sqrt( ( x -= x0 ) * x + ( y -= y0 ) * y );
	}
	if( o && !( o = function( x, y, x0, y0, x1, y1 ){
		if( !( x1 - x0 ) ) return { x: x0, y: y };
		else if( !( y1 - y0 ) ) return { x: x, y: y0 };
		var left, tg = -1 / ( ( y1 - y0 ) / ( x1 - x0 ) );
		return { x: left = ( x1 * ( x * tg - y + y0 ) + x0 * ( x * - tg + y - y1 ) ) / ( tg * ( x1 - x0 ) + y0 - y1 ), y: tg * left - tg * x + y };
	}( x, y, x0, y0, x1, y1 ), o.x >= Math.min( x0, x1 ) && o.x <= Math.max( x0, x1 ) && o.y >= Math.min( y0, y1 ) && o.y <= Math.max( y0, y1 ) ) ){
		var l1 = lineLength( x, y, x0, y0 ), l2 = lineLength( x, y, x1, y1 );
		return l1 > l2 ? l2 : l1;
	}
	else {
		var a = y0 - y1, b = x1 - x0, c = x0 * y1 - y0 * x1;
		return Math.abs( a * x + b * y + c ) / Math.sqrt( a * a + b * b );
	}
};

//+ Jonas Raoni Soares Silva
//@ http://jsfromhell.com/math/dot-line-intersection [v1.0]

dotLineIntersection = function( x, y, x0, y0, x1, y1 ){
	if( !( x1 - x0 ) )
		return { x: x0, y: y };
	else if( !( y1 - y0 ) )
		return { x: x, y: y0 };
	var left, tg = -1 / ( ( y1 - y0 ) / ( x1 - x0 ) );
	return { x: left = ( x1 * ( x * tg - y + y0 ) + x0 * ( x * - tg + y - y1 ) ) / ( tg * ( x1 - x0 ) + y0 - y1 ), y: tg * left - tg * x + y };
};