set Deleted off  
  _screen.FontSize=7  
  clear  
    
  rand(-1)  
  create cursor points (PointId i, coordX i, coordY i, ds b)  
*!*     for lnRow=1 to 10^5  
*!*         insert into points values (lnRow, rnd(), rnd(), 0)  
*!*     endfor  
  insert into points values (1, 7*1024, 7*1024, 0)  
  insert into points values (2, 9*1024, 0, 0)  
    
  replace all ds with sqrt(coordX^2+coordY^2)  
  index on ds tag ds  
  index on bintoc(coordx)+bintoc(coordy) tag xy  
  index on CoordX tag x  
  index on CoordY tag y  
    
    
  nDeltaStart=1024  
  nDeltaStep=8  
    
  nPointX=0  
  nPointY=0
*!*     nPointX=rnd()  
*!*     nPointY=rnd()  
  nDS=sqrt(nPointX^2+nPointY^2)  
    
  for i=1 to 2  
      scan1()  
      scan1()  
      Igor()  
      Igor()  
      Goodwin()  
      Goodwin()  
      Paul()  
      Paul()  
  endfor  
    
  function rnd  
  return 2000000*(rand()-.5)  
    
  function Igor  
      s=seco()  
      lnDelta=nDeltaStart  
      do while _tally=0 or lnDelta=nDeltaStart  
        lnDelta=lnDelta*nDeltaStep  
        select * from points ;  
                where CoordX between nPointX-lnDelta and nPointX+lnDelta ;  
                and CoordY between nPointY-lnDelta and nPointY+lnDelta ;  
                into cursor OutCrs nofilter  
      enddo  
      lnMinDistance=-1    
      lnMinPointId=0  
      scan  
          lnDistance=d()  
          if lnDistance<lnMinDistance or lnMinPointId=0  
              lnMinDistance=lnDistance  
              lnMinPointId=pointId  
          endif  
      endscan  
      use in OutCrs  
      sele points  
      ?'igor', lnMinPointId, lnMinDistance, seco()-s  
  endfunc  
    
  function Paul  
      s=seco()  
      lnDelta=nDeltaStart  
      lnMinDistance=-1    
      lnMinPointId=0  
      set Order To ds  
      set Near on  
      do while lnMinPointId=0 or lnMinDistance>lnDelta  
          seek nDS-lnDelta  
          scan rest while ds<=nDS+lnDelta  
              lnDistance=d()  
              if lnDistance<lnMinDistance or lnMinPointId=0  
                  lnMinDistance=lnDistance  
                  lnMinPointId=pointId  
              endif  
          endscan  
          lnDelta=lnDelta*nDeltaStep  
      enddo  
      set Near off  
      ?'paul', lnMinPointId, lnMinDistance, seco()-s  
  endfunc  
    
  function scan1  
      lnMinDistance=-1    
      lnMinPointId=0   
      s=seco()  
      set Order To   
      scan    
          lnDistance=d()  
          if lnMinDistance=-1 or lnDistance<lnMinDistance    
              lnMinDistance=lnDistance    
              lnMinPointId=PointId    
          endif    
      endscan  
      ?'scan', lnMinPointId, lnMinDistance, seco()-s  
  endfunc  
    
  function goodwin  
      s=seco()  
      set Near On  
      set Order To xy  
      seek bintoc(nPointX)  
      seek bintoc(coordx)+bintoc(nPointY)  
      lnMinDistance=d()  
      lnMinPointId=pointId  
      seek bintoc(nPointX-lnMinDistance)  
      scan rest while coordX<=nPointX+lnMinDistance  
          lnDistance=d()  
          if lnDistance<lnMinDistance  
              lnMinDistance=lnDistance  
              lnMinPointId=pointId  
          endif  
      endscan  
      set Near off  
      ?'goodwin', lnMinPointId, lnMinDistance, seco()-s  
  endfunc  
    
  function d  
  return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)

#DEFINE DEBUG_OUT
#DEFINE START_DELTA 1
#DEFINE DELTA_GROWTH 4
#DEFINE DELTA_REDUCTION 0.7
LOCAL lnSec
lnSec = SECONDS()
? SearchI(50000,1000), SECONDS() - m.lnSec

FUNCTION SearchI (tnX, tnY)
LOCAL lnOldSelect, lnDelta, lnDelta2, lnRes
lnOldSelect = SELECT()
SELECT Points
lnDelta = START_DELTA
#IFDEF DEBUG_OUT
 ? "Start lnDelta:", m.lnDelta
#ENDIF
LOCATE FOR BETWEEN(x, m.tnX-m.lnDelta, m.tnX+m.lnDelta) AND ;
 BETWEEN(Y, m.tnY-m.lnDelta, m.tnY+m.lnDelta)
DO WHILE !FOUND("Points")
 lnDelta = MIN(INT(m.lnDelta*DELTA_GROWTH), 2^31)
 #IFDEF DEBUG_OUT
  ? "Square growth lnDelta:", m.lnDelta
 #ENDIF
 LOCATE FOR BETWEEN(x, m.tnX-m.lnDelta, m.tnX+m.lnDelta) AND ;
  BETWEEN(Y, m.tnY-m.lnDelta, m.tnY+m.lnDelta)
ENDDO
lnDelta2 = m.lnDelta
DO WHILE FOUND("Points") AND m.lnDelta > 1
 lnDelta = m.lnDelta2
 lnDelta2 = FLOOR(m.lnDelta*DELTA_REDUCTION)
 #IFDEF DEBUG_OUT
  ? "Square reduction lnDelta2:", m.lnDelta2
 #ENDIF
 LOCATE FOR BETWEEN(x, m.tnX-m.lnDelta2, m.tnX+m.lnDelta2) AND ;
  BETWEEN(Y, m.tnY-m.lnDelta2, m.tnY+m.lnDelta2)
ENDDO
* lnDelta гарантировано содержащий точку квадрат
#IFDEF DEBUG_OUT
 ? "Stage 1 square lnDelta:", m.lnDelta
#ENDIF
SELECT * FROM Points ;
 WHERE x BETWEEN m.tnX-m.lnDelta AND m.tnX+m.lnDelta ;
 AND Y BETWEEN m.tnY-m.lnDelta AND m.tnY+m.lnDelta ;
 INTO CURSOR t1 NOFILTER
#IFDEF DEBUG_OUT
 ? "Points in stage 1 square:", _TALLY
#ENDIF
SELECT TOP 1 *, ;
 SQRT((m.tnX-x)^2+(m.tnY-Y)^2) Distance ;
 FROM t1 ;
 INTO CURSOR t2 ;
 ORDER BY Distance
IF t2.Distance < m.lnDelta
 #IFDEF DEBUG_OUT
  ? "Solution found in stage 1 square:", t2.ID, t2.x, t2.Y, t2.Distance
 #ENDIF
 lnRes = t2.ID
ELSE
 #IFDEF DEBUG_OUT
  ? "Suboptimal solution found in stage 1 square:", t2.ID, t2.x, t2.Y, t2.Distance
 #ENDIF
 lnDelta = CEILING(t2.Distance)
 #IFDEF DEBUG_OUT
  ? "Stage 2 square lnDelta:", m.lnDelta
 #ENDIF
 SELECT * FROM Points ;
  WHERE x BETWEEN m.tnX-m.lnDelta AND m.tnX+m.lnDelta ;
  AND Y BETWEEN m.tnY-m.lnDelta AND m.tnY+m.lnDelta ;
  INTO CURSOR t1 NOFILTER
 #IFDEF DEBUG_OUT
  ? "Points in stage 2 square:", _TALLY
 #ENDIF
 SELECT TOP 1 *, ;
  SQRT((m.tnX-x)^2+(m.tnY-Y)^2) Distance ;
  FROM t1 ;
  INTO CURSOR t2 ;
  ORDER BY Distance
 #IFDEF DEBUG_OUT
  ? "Solution found in stage 2 square:", t2.ID, t2.x, t2.Y, t2.Distance
 #ENDIF
 lnRes = t2.ID
ENDIF
USE IN SELECT("t2")
USE IN SELECT("t1")
SELECT (m.lnOldSelect)
RETURN m.lnRes
ENDFUNC

  FUNCTION SearchI3 (tnX, tnY)  
  local laRes(1), lnDelta
  lnDelta = START_DELTA  
  LOCATE FOR BETWEEN(x, m.tnX-m.lnDelta, m.tnX+m.lnDelta) AND ;  
   BETWEEN(Y, m.tnY-m.lnDelta, m.tnY+m.lnDelta)  
  DO WHILE !FOUND()
   lnDelta = MIN(INT(m.lnDelta*DELTA_GROWTH), 2^31)  
   LOCATE FOR BETWEEN(x, m.tnX-m.lnDelta, m.tnX+m.lnDelta) AND ;  
    BETWEEN(Y, m.tnY-m.lnDelta, m.tnY+m.lnDelta)  
  ENDDO  
  m.lnDelta=ceil(m.lnDelta*sqrt(2))
  SELECT id, (x-m.tnX)^2+(y-m.tnY)^2 FROM Points ;  
   WHERE x BETWEEN m.tnX-m.lnDelta AND m.tnX+m.lnDelta ;  
   AND Y BETWEEN m.tnY-m.lnDelta AND m.tnY+m.lnDelta ;  
   order by 2 top 1 INTO array laRes
  RETURN laRes(1)