title: Maximum distance between points in a convex hull
body: <p>I am solving a problem in which I need to find the maximum distance between two points on a plane (2D) .So there is an O(n^2) approach in which I calculate distance between every point in the graph . I also implemented a convex hull algorithm now my approach is I compute convex hull in O(nlogn) and then use the O(n^2) algorithm to compute maximum distance between points in the convex hull. Is there a better approach than this to compute the max distance  in convex hull</p>
  
  <p>Here are my algorithm :</p>
  
  <blockquote>
    <p>O(n^2)</p>
  </blockquote>
  
  <pre><code> def d(l1,l2):
      return ((l2[0]-l1[0])**2+(l2[1]-l1[1])**2)
  def find_max_dist(L):
      max_dist = d(L[0], L[1])
      for i in range(0, len(L)-1):
          for j in range(i+1, len(L)):
              max_dist = max(d(L[i], L[j]), max_dist)
      return max_dist
  </code></pre>
  
  <blockquote>
    <p>convex hull</p>
  </blockquote>
  
  <pre><code>def convex_hull(points):
      """Computes the convex hull of a set of 2D points.
  
         Input: an iterable sequence of (x, y) pairs representing the points.
         Output: a list of vertices of the convex hull in counter-clockwise order,
         starting from the vertex with the lexicographically smallest coordinates.
         Implements Andrew's monotone chain algorithm. O(n log n) complexity.
  """
  
        # Sort the points lexicographically (tuples are compared lexicographically).
        # Remove duplicates to detect the case we have just one unique point.
          points = sorted(set(points))
  
        # Boring case: no points or a single point, possibly repeated multiple times.
      if len(points) &lt;= 1:
          return points
  
      # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
      # Returns a positive value, if OAB makes a counter-clockwise turn,
      # negative for clockwise turn, and zero if the points are collinear.
      def cross(o, a, b):
          return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
  
      # Build lower hull
      lower = []
      for p in points:
          while len(lower) &gt;= 2 and cross(lower[-2], lower[-1], p) &lt;= 0:
              lower.pop()
          lower.append(p)
  
      # Build upper hull
      upper = []
      for p in reversed(points):
          while len(upper) &gt;= 2 and cross(upper[-2], upper[-1], p) &lt;= 0:
              upper.pop()
          upper.append(p)
  
      # Concatenation of the lower and upper hulls gives the convex hull.
      # Last point of each list is omitted because it is repeated at the beginning of the other list.
      return lower[:-1] + upper[:-1]
  </code></pre>
  
  <blockquote>
    <p>overall algorithm</p>
  </blockquote>
  
  <pre><code> l=[]
   for i in xrange(int(raw_input())):   # takes input denoting number  of points in the plane
       n=tuple(int(i) for i in raw_input().split())  #takes each point and makes a tuple
       l.append(n)                                # appends to n
  
   if len(l)&gt;=10:
          print find_max_dist(convex_hull(l))
   else:
          print find_max_dist(l)
  </code></pre>
  
  <p>Now how do I improve the running time of my approach and is there a better way to compute this ?</p>