#!/usr/bin/env python

from random import randint
import sys

def mk_sorted_points (num = 256):
   points = [ (randint (0, 100), randint (0, 100))
              for i in range (num) ]
   points.sort ()
   return points


def ori (p, q, r):
   dx1 = q[0] - p[0]
   dy1 = q[1] - p[1]
   dx2 = r[0] - p[0]
   dy2 = r[1] - p[1]

   if dx1*dy2 > dy1*dx2:
      return 1
   elif dx1*dy2 < dy1*dx2:
      return -1
   else:  # Gleichheit
      if (dx1*dx2 < 0) or (dy1*dy2 < 0):
         return -1
      else:
         if (dx1*dx1+dy1*dy1) >= (dx1*dx2 + dy2*dy2):
            return 0
         else:
            return 1


def merge_upper_hull (left, right):
   li = len (left) - 1
   ri = 0

   didsomething = True

   while didsomething:
      didsomething = False
      while (ri < len (right) - 1 and
             ori (left[li], right[ri], right[ri+1]) >= 0):
         didsomething = True
         ri += 1

      while (li > 0 and
             ori (left[li-1], left[li], right[ri]) >= 0):
         didsomething = True
         li -= 1

   return left[:li+1] + right[ri:]


def merge_lower_hull (left, right):
   return merge_upper_hull (right[::-1], left[::-1])[::-1]



def get_convex_hull (points):
   # points ist nach X-Koordinate sortiert
   if len (points) > 2:
      left_points  = points [:len (points)/2]
      right_points = points [len (points)/2:]
      left_upper,  left_lower  = get_convex_hull (left_points)
      right_upper, right_lower = get_convex_hull (right_points)

      upper = merge_upper_hull (left_upper, right_upper)
      lower = merge_lower_hull (left_lower, right_lower)
      return (upper, lower)
   else:
      return points[:], points[:]



def ps_header ():
   print """%!PS-Adobe-3.0

      /Spot { newpath 0.4 0 360 arc closepath fill } def

      47.5 171 translate
      5 5 scale
      0.2 setlinewidth
      """
   
def ps_plot_points (points):
   for p in points:
      print "%3d %3d Spot" % p

def ps_plot_polyline (points):
   print "newpath"
   print "%3d %3d moveto" % points [0]

   for p in points[1:]:
      print "%3d %3d lineto" % p
   print "stroke"

def ps_footer ():
   print "showpage"

if __name__=='__main__':
   ps_header ()
   p = mk_sorted_points (28)
   upper, lower = get_convex_hull (p)
   ps_plot_polyline (upper)
   ps_plot_polyline (lower)
   ps_plot_points (p)
   ps_footer ()