Closest-pair problem: Difference between revisions

<lang rexx>/*REXX program solves the closest pair of points problem (in two dimensions). */

parse arg N low high seed . /*obtain optional arguments from the CL*/

if N=='' | N=='",'" then N= 100 /*Not specified? Then use the default.*/

if low=='' | low=='",'" then low= 0 /* " " " " " " */

if high=='' | high=='",'" then high=20000 /* " " " " " " */

if datatype(seed,'W') then call random ,,seed /*seed for RANDOM repeatable(BIF) repeatability.*/

/*╔══════════════════════╗*/ do j=1 for N /*generate N random points. */

/*║ generate N points. ║*/ @x.j=random(low,high) /* " /*a random X. */

/*╚══════════════════════╝*/ @y.j=random(low,high) /* /*" " " Y. */

end /*j*/ /*X and Y make the point*/

minDD=(@x.A-@x.B)**2 + (@y.A-@y.B)**2 /*distance between the first two points. */

do j=1 for N-1 /*find minimum distance between a ··· */

do k=j+1 to N /* ··· point and all the other points.*/

dd=(@x.j - @x.k)**2 + (@y.j - @y.k)**2 /*compute squared distance from points.*/

if dd\=0<minDD then if dd<minDD \=0 then do;parse value minDD=dd; A=j; B=k; end with minDD A B

end /*k*/ /* [+] needn't take SQRT of DD (yet).*/

end /*j*/ /* [↑] when done, A & B are the ones*/

_= 'For ' N " points, the minimum distance between the two points: "

say _ center("x", w, '═')" " center('y', w, "═") ' is: ' sqrt(abs(minDD))/1

say left('', length(_)-1) ' "['"right(@x.A, w)"',"' right(@y.A, w)"]"

say left('', length(_)-1) ' "['"right(@x.B, w)"',"' right(@y.B, w)"]"

exit /*stick a fork in it, we're all done. */

sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); im.=9; numeric form; m.h=9d+6

numeric digits 9; numericparse form;value h=d+6;format(x,2,1,,0) 'E0' if x<0with theng 'E' do_ .; x g=-x;g i=*.5'ie';_ % end2

parse value format(x,2,1,, do j=0) 'E0' while withh>9; g 'E' _ m.j=h; g h=g*.5'e'_h%2+1; end /*j*/

do j=0 while h>9; do m.k=j=h;+5 to 0 by -1; numeric digits m.k; hg=h%2(g+1x/g)*.5; end /*jk*/