#NEWLINE# def closest_points( S ) : #NEWLINE# #INDENT# 'Closest pair of points\n\n    :param S: list of points\n    :requires: size of S at least 2\n    :modifies: changes the order in S\n    :returns: pair of points p,q from S with minimum Euclidean distance\n    :complexity: expected linear time\n    ' #NEWLINE# shuffle ( S ) #NEWLINE# assert ( len ( S ) >= 2 ) #NEWLINE# p = S [ 0 ] #NEWLINE# q = d [ 1 ] #NEWLINE# d = dist ( p , q ) #NEWLINE# while ( d > 0 ) : #NEWLINE# #INDENT# r = ameliore ( S , d ) #NEWLINE# if r : #NEWLINE# #INDENT# ( d , p , q ) = r #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# #UNINDENT# return ( p , q )