function [ d, kout, jout ] = divcon ( z ,~ )

%*****************************************************************************80
%
%% divcon() finds the closest pair of points in 2d using divide and conquer.
%
%  Discussion:
%
%    The algorithm is recursive, and uses an auxilliary function center()
%    to examine the center strip.
%
%  License:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    13 August 2024
%
%  Author:
%
%    Original MATLAB code by Cleve Moler.
%    This version by John Burkardt.
%
%  Reference:
%
%    Cleve Moler,
%    https://blogs.mathworks.com/cleve/2024/03/28/closest-pair-of-points-problem/
%    Closest pair of points problem,
%    28 March 2024.
%
%  Input:
%
%    complex z(n): the X and Y coordinates of the points.
%
%    integer p(n): an index of the points, sorted by the real part,
%    which is generally not included in the user level call, but is
%    internally generated on the first call and passed to the recursive
%    calls.
%
%  Output:
%
%    real d: the distance of the closest pair.
%
%    integer i, j: the indices of the closest pair.
%
  n = length ( z );

  if ( n <= 3 )
    [ d, kout, jout ] = brute ( z );
    return
  end

  if ( nargin < 2 )
    [ ~, p ] = sort ( real ( z ) );
    z = z(p);
  else
    p = (1:n)';
  end

  m = floor ( n / 2 );
%
%  Left half.
%
  [ dl, kl, jl ] = divcon ( z(1:m), true );
%
%  Right half.
%
  [ dr, kr, jr ] = divcon ( z(m+1:end), true );
%
%  Remember the better of the left and right results.
%
  if ( dl < dr )
    d = dl; 
    k = kl;
    j = jl;
  else
    d = dr;
    k = kr + m;
    j = jr + m;
  end
%
%  Center strip.
%
  [ ds, ks, js ] = center ( z, d );
  if ds < d
    d = ds;
    k = ks;
    j = js;
  end

  kout = min ( p(k), p(j) );
  jout = max ( p(k), p(j) );

  return
end
