package Ġstructures Ċ Ċ import Ġjava . util . Random Ċ Ċ // Ġhttps :// en . wikipedia . org / wiki / Metric _ tree Ċ class ĠMetric Tree ( var Ġx : ĠInt Array , Ġvar Ġy : ĠInt Array ) Ġ{ ĊĠĠĠ Ġfun Ġbuild ( low : ĠInt , Ġhigh : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( high Ġ- Ġlow Ġ<= Ġ 2 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġswap ( low Ġ+ Ġrnd . nextInt ( high Ġ- Ġlow ), Ġlow ) ĊĠĠĠĠĠĠĠ Ġval Ġmid Ġ= Ġlow Ġ+ Ġ 1 Ġ+ Ġhigh Ġ ush r Ġ 1 ĊĠĠĠĠĠĠĠ Ġnth _ element ( low Ġ+ Ġ 1 , Ġhigh , Ġmid ) ĊĠĠĠĠĠĠĠ Ġbuild ( low Ġ+ Ġ 1 , Ġmid ) ĊĠĠĠĠĠĠĠ Ġbuild ( mid Ġ+ Ġ 1 , Ġhigh ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠSee Ġhttp :// www . cplusplus . com / reference / algorithm / nth _ element ĊĠĠĠ Ġfun Ġnth _ element ( low : ĠInt , Ġhigh : ĠInt , Ġn : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġlow Ġ= Ġlow ĊĠĠĠĠĠĠĠ Ġvar Ġhigh Ġ= Ġhigh ĊĠĠĠĠĠĠĠ Ġval Ġcenter Ġ= Ġlow Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġpartition ( center , Ġlow , Ġhigh , Ġlow Ġ+ Ġrnd . nextInt ( high Ġ- Ġlow )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Ġ< Ġk ) Ġhigh Ġ= Ġk Ġelse Ġif Ġ( n Ġ> Ġk ) Ġlow Ġ= Ġk Ġ+ Ġ 1 Ġelse Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġpartition ( center : ĠInt , Ġfrom Inclusive : ĠInt , Ġto Exclusive : ĠInt , Ġseparator Index : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġfrom Inclusive ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġto Exclusive Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( i Ġ>= Ġj ) Ġreturn Ġj ĊĠĠĠĠĠĠĠ Ġval Ġseparator Ġ= Ġdist 2 ( x [ center ], Ġy [ center ], Ġx [ separator Index ], Ġy [ separator Index ]) ĊĠĠĠĠĠĠĠ Ġswap ( i ++, Ġseparator Index ) ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ<= Ġj ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ<= Ġj Ġ&& Ġdist 2 ( x [ center ], Ġy [ center ], Ġx [ i ], Ġy [ i ]) Ġ< Ġseparator ) Ġ++ i ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ<= Ġj Ġ&& Ġdist 2 ( x [ center ], Ġy [ center ], Ġx [ j ], Ġy [ j ]) Ġ> Ġseparator ) Ġ-- j ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( i Ġ>= Ġj ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġswap ( i ++, Ġj --) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġswap ( j , Ġfrom Inclusive ) ĊĠĠĠĠĠĠĠ Ġreturn Ġj ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġswap ( i : ĠInt , Ġj : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġx [ i ] ĊĠĠĠĠĠĠĠ Ġx [ i ] Ġ= Ġx [ j ] ĊĠĠĠĠĠĠĠ Ġx [ j ] Ġ= Ġt ĊĠĠĠĠĠĠĠ Ġt Ġ= Ġy [ i ] ĊĠĠĠĠĠĠĠ Ġy [ i ] Ġ= Ġy [ j ] ĊĠĠĠĠĠĠĠ Ġy [ j ] Ġ= Ġt ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġvar Ġbest Dist : ĠLong Ġ= Ġ 0 ĊĠĠĠ Ġvar Ġbest Node Ġ= Ġ 0 ĊĠĠĠ Ġfun Ġfind Nearest Ne ighbour ( px : ĠInt , Ġpy : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġbest Dist Ġ= ĠLong . MAX _ VALUE ĊĠĠĠĠĠĠĠ Ġfind Nearest Ne ighbour ( 0 , Ġx . size , Ġpx , Ġpy ) ĊĠĠĠĠĠĠĠ Ġreturn Ġbest Node ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfind Nearest Ne ighbour ( low : ĠInt , Ġhigh : ĠInt , Ġpx : ĠInt , Ġpy : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( high Ġ- Ġlow Ġ<= Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġd 2 Ġ= Ġdist 2 ( px , Ġpy , Ġx [ low ], Ġy [ low ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( best Dist Ġ> Ġd 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbest Dist Ġ= Ġd 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbest Node Ġ= Ġlow ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( high Ġ- Ġlow Ġ<= Ġ 1 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġmid Ġ= Ġlow Ġ+ Ġ 1 Ġ+ Ġhigh Ġ ush r Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġdist 2 Ġ= Ġdist 2 ( px , Ġpy , Ġx [ mid ], Ġy [ mid ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( best Dist Ġ> Ġdist 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbest Dist Ġ= Ġdist 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġbest Node Ġ= Ġmid ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval ĠR : ĠDouble Ġ= ĠMath . sqrt ( dist 2 ( x [ low ], Ġy [ low ], Ġx [ mid ], Ġy [ mid ])) ĊĠĠĠĠĠĠĠ Ġval Ġr : ĠDouble Ġ= ĠMath . sqrt ( best Dist ) ĊĠĠĠĠĠĠĠ Ġval Ġd : ĠDouble Ġ= ĠMath . sqrt ( d 2 ) ĊĠĠĠĠĠĠĠ Ġif Ġ( d Ġ<= ĠR Ġ+ Ġr ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfind Nearest Ne ighbour ( low Ġ+ Ġ 1 , Ġmid , Ġpx , Ġpy ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( d Ġ>= ĠR Ġ- Ġr ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfind Nearest Ne ighbour ( mid Ġ+ Ġ 1 , Ġhigh , Ġpx , Ġpy ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġrnd : ĠRandom Ġ= ĠRandom ( 1 ) ĊĠĠĠĠĠĠĠ Ġfun Ġdist 2 ( x 1 : ĠInt , Ġy 1 : ĠInt , Ġx 2 : ĠInt , Ġy 2 : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdx Ġ= Ġx 1 Ġ- Ġx 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdy Ġ= Ġy 1 Ġ- Ġy 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġdx . to Long () Ġ* Ġdx Ġ+ Ġdy . to Long () Ġ* Ġdy ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġrandom Ġtest ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String ?> ?) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( step Ġin Ġ 0 .. 9 9 9 9 9 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġq x : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ- Ġ 5 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġq y : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ- Ġ 5 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx Ġ= ĠInt Array ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy Ġ= ĠInt Array ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmin Dist Ġ= ĠLong . MAX _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx [ i ] Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ- Ġ 5 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy [ i ] Ġ= Ġrnd . nextInt ( 1 0 0 ) Ġ- Ġ 5 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmin Dist Ġ= ĠMath . min ( min Dist , Ġdist 2 ( qx , Ġq y , Ġx [ i ], Ġy [ i ])) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġmetric Tree Ġ= ĠMetric Tree ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġindex Ġ= Ġmetric Tree . find Nearest Ne ighbour ( qx , Ġq y ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( min Dist Ġ!= Ġmetric Tree . best Dist Ġ|| Ġdist 2 ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq x , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq y , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx [ index ], ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġy [ index ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ!= Ġmin Dist ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġbuild ( 0 , Ġx . size ) ĊĠĠĠ Ġ} Ċ } Ċ