cdeck homr12
      subroutine homr12 (n,x,m,in,ii,jj,s,iabv,na,maxa,ibel,nb,maxb)
c this subroutine takes the m points of array x whose
c subscripts are in array in and partitions them by the
c line joining the two points in array x whose subscripts
c are ii and jj.  the subscripts of the points above the
c line are put into array iabv, and the subscripts of the
c points below are put into array ibel.  na and nb are,
c respectively, the number of points above the line and the
c number below.  maxa and maxb are the subscripts for array
c x of the point furthest above the line and the point
c furthest below, respectively.  if either subset is null
c the corresponding subscript (maxa or maxb) is set to zero
c formal parameters
c input
c n    integer           total number of data points
c x    real array (2,n)  (x,y) co-ordinates of the data
c m    integer           number of points in input subset
c in   integer array (m) subscripts for array x of the
c                        points in the input subset
c ii   integer           subscripts for array x of one point
c                        on the partitioning line
c jj   integer           subscript for array x of another
c                        point on the partitioning line
c s    integer           switch to determine output.  refer
c                        to comments below
c
c output
c iabv integer array (m) subscripts for array x of the
c                        points above the partitioning line
c na   integer           number of elements in iabv
c maxa integer           subscript for array x of point
c                        furthest above the line.  set to
c                        zero if na is zero
c ibel integer array (m) subscripts for array x of the
c                        points below the partitioning line
c nb   integer           number of elements in ibel
c maxb integer           subscript for array x of point
c                        furthest below the line.  set to
c                        zero if nb is zero
      dimension x(3,n)
      dimension in(m), iabv(m), ibel(m)
      integer s
c if s = 2 dont save ibel, nb, maxb
c if s =-2 dont save iabv, na, maxa
c otherwise save everything
c if s is positive the array being partitioned is above
c the initial partitioning line.  if it is negative, then
c the set of points is below.
      logical   t
      t=.false.
c check to see if the line is veritical
      if (x(1,jj).ne.x(1,ii)) go to 10
      xt=x(1,ii)
      dir=sign(1.,x(2,jj)-x(2,ii))*sign(1.,float(s))
      t=.true.
      go to 20
   10 a=(x(2,jj)-x(2,ii))/(x(1,jj)-x(1,ii))
      b=x(2,ii)-a*x(1,ii)
   20 up=0.
      na=0
      maxa=0
      down=0.
      nb=0
      maxb=0
      do 60 i=1,m
         is=in(i)
      if (t) go to 30
      z=x(2,is)-a*x(1,is)-b
      go to 40
   30 z=dir*(x(1,is)-xt)
   40 if (z.le.0.) go to 50
c the point is above the line
      if (s.eq.-2) go to 60
      na=na+1
      iabv(na)=is
      if (z.lt.up) go to 60
      up=z
      maxa=na
      go to 60
   50 if (s.eq.2) go to 60
      if (z.ge.0.) go to 60
c the point is below the line
      nb=nb+1
      ibel(nb)=is
      if (z.gt.down) go to 60
      down=z
      maxb=nb
   60 continue
      return
      end