def linearNearestNeighbors(A,B):
    '''Takes as input a set of points A and B in some Euclidean space.
    A lies on the x-axis and is given as a sequence of real numbers;
    B is given in Cartesian coordinates (tuples of real numbers).
    Output is a dict mapping each point in A to the nearest point in B.'''

    # negate squared Euclidean distance to convert minimization of distance
    # into a maximization problem suitable for SMAWK algorithm
    def square(x): return x*x
    def negDist(a,b):
        dist = square(b[0]-a)
        for i in range(1,len(b)):
            dist += square(b[i])
        return -dist
	
    A.sort()	# make sure points are sorted, omit if already sorted
    B.sort()
    return smawk(A,B,negDist)
Takes as input a set of points A and B in some Euclidean space.
    A lies on the x-axis and is given as a sequence of real numbers;
    B is given in Cartesian coordinates (tuples of real numbers).
    Output is a dict mapping each point in A to the nearest point in B.
recipes/Python/117244_SMAWK_totally_monotone_matrix_searching/recipe-117244.py