%!

(sort.inc) run

/hulldict 32 dict def

hulldict begin

% u - v 

/vsub { 2 dict begin
/v exch def
/u exch def
[ 
  u 0 get v 0 get sub
  u 1 get v 1 get sub
]
end } def

% u - v rotated 90 degrees

/vperp { 2 dict begin
/v exch def
/u exch def
[ 
  v 1 get u 1 get sub
  u 0 get v 0 get sub
]
end } def

/dot { 2 dict begin
/v exch def
/u exch def
  v 0 get u 0 get mul
  v 1 get u 1 get mul
  add
end } def 

% P Q
% tests whether P < Q in lexicographic order
% i.e xP < xQ, or yP < yQ if xP = yP

/comp { 2 dict begin
/Q exch def
/P exch def
P 0 get Q 0 get lt 
  P 0 get Q 0 get eq
  P 1 get Q 1 get lt 
  and 
or 
end } def

end

% args: an arrya of points C
% effect: returns the array of points on the boundary of
%     the convex hull of C, in clockwise order 

/hull { hulldict begin
/C exch def
/comp C quicksort
/n C length def
% Q might circle around to the start
/Q n 1 add array def
Q 0 C 0 get put
Q 1 C 1 get put
/i 2 def
/k 2 def
% i is next point in C to be looked at
% k is next point in Q to be added
% [ Q[0] Q[1] ... ]
% scan the points to make the top hull
n 2 sub {
  % P is the current point at right
  /P C i get def
  /i i 1 add def
  {
    % if k = 1 then just add P 
    k 2 lt { exit } if
    % now k is 2 or more
    % look at Q[k-2] Q[k-1] P: a left turn (or in a line)?
    % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0
    P Q k 1 sub get vsub 
    Q k 1 sub get Q k 2 sub get vperp 
    dot 0 lt {
      % not a left turn
      exit
    } if
    /k k 1 sub def
  } loop
  Q k P put
  /k k 1 add def
} repeat

% done with top half
% K is where the right hand point is
/K k 1 sub def

/i n 2 sub def
Q k C i get put
/i i 1 sub def
/k k 1 add def
n 2 sub {
  % P is the current point at right
  /P C i get def
  /i i 1 sub def
  {
    % in this pass k is always 2 or more
    k K 2 add lt { exit } if
    % look at Q[k-2] Q[k-1] P: a left turn (or in a line)?
    % yes if (P - Q[k-1])*(Q[k-1] - Q[k-2])^perp >= 0
    P Q k 1 sub get vsub 
    Q k 1 sub get Q k 2 sub get vperp 
    dot 0 lt {
      % not a left turn
      exit
    } if
    /k k 1 sub def
  } loop
  Q k P put
  /k k 1 add def
} repeat

% strip Q down to [ Q[0] Q[1] ... Q[k-2] ]
% excluding the doubled initial point
[ 0 1 k 2 sub {
  Q exch get
} for ] 
end } def