(* arbre 2-dimensionnel *)

let d = 2;; 

type point = float array;; (* tableaux de longueur d *)

type kdtree = V | N of kdtree * point * kdtree;; 

let pt_test = [|
  [| 87.4 ; 28.3 |];
  [| 38.6 ; 35.3 |];
  [| 87.0 ; 31.1 |];
  [| 26.1 ; 27.5 |];
  [| 58.8 ; 35.3 |];
  [| 72.3 ; 13.5 |];
  [| 80.0 ; 9.8 |];
  [| 56.0 ; 44.3 |];
  [| 61.2 ; 10.4 |];
  [| 49.4 ; 10.2 |];
  [| 51.4 ; 50.1 |];
  [| 54.9 ; 19.2 |];
  [| 17.9 ; 9.6 |];
  [| 94.4 ; 14.3 |];
  [| 8.8 ; 34.0 |];
  [| 71.4 ; 3.3 |];
  [| 27.7 ; 61.7 |];
  [| 84.6 ; 32.9 |];
  [| 39.7 ; 50.4 |];
  [| 44.4 ; 9.1 |];
  [| 31.8 ; 22.5 |];
  [| 70.9 ; 43.3 |];
  [| 9.7 ; 59.2 |];
  [| 70.8 ; 26.5 |];
  [| 44.8 ; 20.7 |];
  [| 40.1 ; 10.9 |];
  [| 5.8 ; 32.9 |];
  [| 26.0 ; 48.7 |];
  [| 60.4 ; 46.6 |];
  [| 67.8 ; 57.2 |];
  [| 41.6 ; 64.3 |];
  [| 83.5 ; 38.5 |];
  [| 89.2 ; 3.5 |];
  [| 63.3 ; 17.7 |];
  [| 57.4 ; 31.4 |];
  [| 53.6 ; 38.6 |];
  [| 27.3 ; 61.4 |];
  [| 14.4 ; 4.9 |];
  [| 8.0 ; 7.0 |];
  [| 69.2 ; 22.0 |];
  [| 57.1 ; 32.6 |];
  [| 43.8 ; 58.8 |];
  [| 89.1 ; 60.1 |];
  [| 46.2 ; 24.1 |];
  [| 93.3 ; 61.9 |];
  [| 44.1 ; 30.8 |];
  [| 71.8 ; 27.5 |];
  [| 26.1 ; 27.4 |];
  [| 91.8 ; 43.4 |];
  [| 23.1 ; 56.1 |];
  [| 90.3 ; 16.8 |];
  [| 65.0 ; 25.9 |];
  [| 47.8 ; 32.1 |];
  [| 45.9 ; 22.5 |];
  [| 8.9 ; 57.9 |];
  [| 86.5 ; 20.7 |];
  [| 38.8 ; 41.3 |];
  [| 17.5 ; 60.7 |];
  [| 76.8 ; 53.1 |];
  [| 70.0 ; 43.2 |];
  [| 36.8 ; 24.2 |];
  [| 88.7 ; 25.5 |];
  [| 7.1 ; 20.1 |];
  [| 11.3 ; 49.7 |];
  [| 50.1 ; 39.2 |];
  [| 78.8 ; 46.5 |];
  [| 22.5 ; 35.6 |];
  [| 40.4 ; 15.5 |];
  [| 74.9 ; 60.2 |];
  [| 46.6 ; 12.9 |];
  [| 55.5 ; 55.4 |];
  [| 40.9 ; 59.7 |];
  [| 74.6 ; 45.7 |];
  [| 25.4 ; 39.5 |];
  [| 77.9 ; 8.3 |];
  [| 18.3 ; 51.2 |];
  [| 38.5 ; 33.6 |];
  [| 63.2 ; 26.4 |];
  [| 65.7 ; 37.2 |];
  [| 73.8 ; 4.4 |];
  [| 91.9 ; 11.7 |];
  [| 30.5 ; 46.6 |];
  [| 44.4 ; 43.1 |];
  [| 83.2 ; 28.6 |];
  [| 79.3 ; 33.2 |];
  [| 92.9 ; 43.1 |];
  [| 79.4 ; 24.2 |];
  [| 20.2 ; 33.3 |];
  [| 32.6 ; 18.7 |];
  [| 93.4 ; 27.4 |];
  [| 23.1 ; 63.9 |];
  [| 80.8 ; 27.9 |];
  [| 33.3 ; 50.8 |];
  [| 81.4 ; 32.8 |];
  [| 75.2 ; 11.7 |];
  [| 49.9 ; 14.3 |];
  [| 71.5 ; 30.6 |];
  [| 18.4 ; 45.2 |];
  [| 69.6 ; 22.7 |];
  [| 0.8 ; 42.8 |];
  [| 56.3 ; 31.3 |];
  [| 78.3 ; 62.0 |];
  [| 49.0 ; 24.6 |];
  [| 65.7 ; 63.1 |];
  [| 71.9 ; 12.8 |];
  [| 2.8 ; 37.4 |];
  [| 61.6 ; 34.7 |];
  [| 64.3 ; 7.9 |];
  [| 18.8 ; 37.9 |];
  [| 16.3 ; 48.9 |];
  [| 49.2 ; 41.2 |];
  [| 86.7 ; 2.3 |];
  [| 82.6 ; 4.1 |];
  [| 22.2 ; 11.3 |];
  [| 89.5 ; 29.2 |];
  [| 61.0 ; 48.5 |];
  [| 19.1 ; 15.3 |];
  [| 13.6 ; 10.5 |];
  [| 37.7 ; 39.5 |];
  [| 62.0 ; 56.4 |];
  [| 8.1 ; 41.6 |];
  [| 81.4 ; 39.6 |];
  [| 59.6 ; 33.3 |];
  [| 42.2 ; 28.8 |];
  [| 24.2 ; 38.7 |];
  [| 33.7 ; 30.7 |];
  [| 76.3 ; 9.9 |];
  [| 65.9 ; 7.4 |];
  [| 48.0 ; 30.6 |];
  [| 54.2 ; 15.8 |];
  [| 7.5 ; 59.3 |];
  [| 20.1 ; 5.3 |];
  [| 45.7 ; 13.8 |];
  [| 22.1 ; 26.5 |];
  [| 72.0 ; 23.3 |];
  [| 50.6 ; 43.0 |];
  [| 54.0 ; 7.6 |];
  [| 63.4 ; 60.0 |];
  [| 63.1 ; 24.9 |];
  [| 2.8 ; 52.3 |];
  [| 62.6 ; 23.6 |];
  [| 48.5 ; 27.6 |];
  [| 3.3 ; 39.5 |];
  [| 90.1 ; 43.5 |];
  [| 15.6 ; 12.1 |];
  [| 14.6 ; 12.7 |];
  [| 45.9 ; 62.1 |];
  [| 84.7 ; 7.4 |];
  [| 67.5 ; 7.3 |];
  [| 18.1 ; 16.4 |];
  [| 39.6 ; 14.6 |];
  [| 3.3 ; 12.5 |];
  [| 62.9 ; 13.8 |];
  [| 81.8 ; 16.6 |];
  [| 16.9 ; 61.9 |];
  [| 72.3 ; 37.0 |];
  [| 62.9 ; 63.9 |];
  [| 84.5 ; 7.5 |];
  [| 56.0 ; 26.3 |];
  [| 14.3 ; 60.1 |];
  [| 88.9 ; 60.8 |];
  [| 90.0 ; 15.7 |];
  [| 9.6 ; 19.1 |];
  [| 64.4 ; 63.4 |];
  [| 90.1 ; 41.4 |];
  [| 30.3 ; 57.0 |];
  [| 53.8 ; 60.0 |];
  [| 43.2 ; 32.6 |];
  [| 43.4 ; 35.1 |];
  [| 35.0 ; 3.8 |];
  [| 93.9 ; 48.1 |];
  [| 4.3 ; 6.8 |];
  [| 10.6 ; 50.0 |];
  [| 58.0 ; 7.3 |];
  [| 88.1 ; 24.4 |];
  [| 67.3 ; 26.7 |];
  [| 73.8 ; 30.9 |];
  [| 2.8 ; 28.9 |];
  [| 83.4 ; 25.6 |];
  [| 83.2 ; 49.4 |];
  [| 86.1 ; 18.0 |];
  [| 63.7 ; 61.6 |];
  [| 36.6 ; 5.9 |];
  [| 64.7 ; 8.2 |];
  [| 86.0 ; 39.1 |];
  [| 71.0 ; 26.3 |];
  [| 44.9 ; 10.7 |];
  [| 1.8 ; 17.1 |];
  [| 84.7 ; 52.1 |];
  [| 60.3 ; 8.5 |];
  [| 70.1 ; 24.1 |];
  [| 27.7 ; 41.4 |];
  [| 78.0 ; 9.6 |];
  [| 75.0 ; 60.0 |];
  [| 16.8 ; 22.1 |];
  [| 78.5 ; 44.6 |];
  [| 92.7 ; 1.9 |];
  [| 68.8 ; 7.9 |];
  [| 33.9 ; 55.4 |];
  [| 21.6 ; 28.4 |];
  [| 64.9 ; 19.4 |];
  [| 82.5 ; 31.2 |];
  [| 24.5 ; 9.6 |];
  [| 68.3 ; 16.2 |];
  [| 95.0 ; 24.0 |];
  [| 73.3 ; 30.6 |];
  [| 32.8 ; 35.8 |];
  [| 94.2 ; 58.1 |];
  [| 84.9 ; 2.5 |];
  [| 28.3 ; 1.1 |];
  [| 74.3 ; 37.1 |];
  [| 20.0 ; 62.6 |];
  [| 40.0 ; 44.9 |];
  [| 10.3 ; 64.8 |];
  [| 35.5 ; 57.0 |];
  [| 67.6 ; 22.2 |];
  [| 10.1 ; 15.6 |];
  [| 48.3 ; 5.1 |];
  [| 47.8 ; 47.3 |];
  [| 26.7 ; 42.6 |];
  [| 1.7 ; 64.6 |];
  [| 59.9 ; 41.9 |];
  [| 47.8 ; 14.5 |];
  [| 64.7 ; 18.2 |];
  [| 58.4 ; 20.9 |];
  [| 18.8 ; 5.8 |];
  [| 26.1 ; 10.8 |];
  [| 42.0 ; 16.0 |];
  [| 94.2 ; 8.3 |];
  [| 50.7 ; 40.4 |];
  [| 77.0 ; 38.9 |];
  [| 13.8 ; 35.8 |];
  [| 75.6 ; 40.2 |];
  [| 90.6 ; 62.4 |];
  [| 57.6 ; 65.0 |];
  [| 41.1 ; 43.4 |];
  [| 82.5 ; 3.2 |];
  [| 12.7 ; 27.2 |];
  [| 79.4 ; 34.7 |];
  [| 50.5 ; 63.4 |];
  [| 69.2 ; 7.1 |];
  [| 45.5 ; 60.6 |];
  [| 34.4 ; 32.9 |];
  [| 59.9 ; 26.3 |];
  [| 75.5 ; 21.6 |];
  [| 83.8 ; 51.7 |];
  [| 21.5 ; 19.3 |];
  [| 72.3 ; 47.7 |];
  [| 73.0 ; 62.9 |];
  [| 13.8 ; 10.3 |];
  [| 78.9 ; 35.6 |];
  [| 1.1 ; 31.4 |];
  [| 28.5 ; 54.8 |];
  [| 68.2 ; 54.1 |];
  [| 6.7 ; 54.0 |];
  [| 35.0 ; 64.7 |];
  [| 26.2 ; 15.4 |];
  [| 69.0 ; 2.5 |];
  [| 17.3 ; 28.8 |];
  [| 26.2 ; 30.8 |];
  [| 2.5 ; 16.4 |];
  [| 61.4 ; 12.9 |];
  [| 6.1 ; 37.8 |];
  [| 14.4 ; 10.7 |];
  [| 32.4 ; 1.2 |];
  [| 37.9 ; 30.0 |];
  [| 76.6 ; 14.5 |];
  [| 64.7 ; 29.5 |];
  [| 11.3 ; 57.7 |];
  [| 25.4 ; 15.6 |];
  [| 73.2 ; 32.1 |];
  [| 77.2 ; 14.4 |];
  [| 88.6 ; 8.5 |];
  [| 63.9 ; 35.4 |];
  [| 86.5 ; 12.0 |];
  [| 26.1 ; 41.2 |];
  [| 13.1 ; 41.9 |];
  [| 54.2 ; 63.9 |];
  [| 23.3 ; 42.4 |];
  [| 47.3 ; 13.2 |];
  [| 90.0 ; 42.6 |];
  [| 41.8 ; 9.9 |];
  [| 36.7 ; 4.5 |];
  [| 18.8 ; 26.6 |];
  [| 74.3 ; 8.3 |];
  [| 15.8 ; 15.7 |];
  [| 42.8 ; 18.1 |];
  [| 69.9 ; 57.6 |];
  [| 47.3 ; 6.0 |];
  [| 1.0 ; 48.8 |];
  [| 81.9 ; 46.0 |];
  [| 88.1 ; 17.8 |];
  [| 20.9 ; 56.9 |];
  [| 77.0 ; 48.2 |];
  [| 61.3 ; 16.8 |];
  [| 12.2 ; 10.9 |];
  [| 32.0 ; 3.7 |];
  [| 62.0 ; 2.6 |];
  [| 58.4 ; 60.1 |];
  [| 85.0 ; 52.7 |];
  [| 88.3 ; 61.4 |];
  [| 9.8 ; 64.2 |];
  [| 89.5 ; 7.5 |];
  [| 12.4 ; 41.4 |];
  [| 42.0 ; 7.1 |];
  [| 24.4 ; 44.6 |];
  [| 90.3 ; 51.5 |];
  [| 44.5 ; 47.2 |];
  [| 55.7 ; 56.7 |];
  [| 86.1 ; 54.7 |];
  [| 79.5 ; 11.6 |];
  [| 7.0 ; 23.6 |];
  [| 59.6 ; 18.2 |];
  [| 51.0 ; 57.5 |];
  [| 12.9 ; 25.7 |];
  [| 25.2 ; 15.8 |];
  [| 62.6 ; 11.6 |];
  [| 91.6 ; 26.2 |];
  [| 42.9 ; 25.8 |];
  [| 89.3 ; 53.9 |];
  [| 74.7 ; 26.4 |];
  [| 50.2 ; 59.4 |];
  [| 57.4 ; 47.0 |];
  [| 67.5 ; 52.5 |];
  [| 71.5 ; 20.3 |];
  [| 28.8 ; 15.0 |];
  [| 47.7 ; 32.3 |];
  [| 81.4 ; 51.9 |];
  [| 65.2 ; 48.8 |];
  [| 47.2 ; 23.0 |];
  [| 75.8 ; 22.1 |];
  [| 51.3 ; 46.2 |];
  [| 31.6 ; 20.6 |];
  [| 10.4 ; 49.2 |];
  [| 27.7 ; 16.9 |];
  [| 30.6 ; 39.3 |];
  [| 3.1 ; 11.7 |];
  [| 7.8 ; 57.2 |];
  [| 17.2 ; 13.8 |];
  [| 74.4 ; 13.2 |];
  [| 58.9 ; 63.6 |];
  [| 24.3 ; 2.1 |];
  [| 40.7 ; 7.9 |];
  [| 41.2 ; 57.9 |];
  [| 15.2 ; 34.5 |];
  [| 88.3 ; 17.4 |];
  [| 76.9 ; 33.7 |];
  [| 6.3 ; 7.0 |];
  [| 87.3 ; 12.5 |];
  [| 31.8 ; 52.8 |];
  [| 17.8 ; 38.2 |];
  [| 87.6 ; 62.5 |];
  [| 62.3 ; 32.8 |];
  [| 26.8 ; 42.8 |];
  [| 79.2 ; 28.1 |];
  [| 61.0 ; 5.5 |];
  [| 59.5 ; 51.4 |];
  [| 12.5 ; 50.2 |];
  [| 61.0 ; 42.1 |];
  [| 12.7 ; 55.2 |];
  [| 36.6 ; 48.1 |];
  [| 77.2 ; 39.5 |];
  [| 71.1 ; 31.4 |];
  [| 81.0 ; 12.8 |];
  [| 82.7 ; 8.1 |];
  [| 30.7 ; 22.6 |];
  [| 75.0 ; 63.7 |];
  [| 67.1 ; 16.2 |];
  [| 42.3 ; 56.5 |];
  [| 94.1 ; 7.8 |];
  [| 67.9 ; 3.5 |];
  [| 84.7 ; 28.6 |];
  [| 65.0 ; 3.1 |];
  [| 26.4 ; 22.2 |];
  [| 14.6 ; 47.1 |];
  [| 16.1 ; 34.6 |];
  [| 23.4 ; 50.9 |];
  [| 72.7 ; 31.3 |];
  [| 28.4 ; 18.2 |];
  [| 67.1 ; 14.1 |];
  [| 75.4 ; 40.0 |];
  [| 83.3 ; 27.9 |];
  [| 2.2 ; 5.1 |];
  [| 1.4 ; 10.9 |];
  [| 63.7 ; 12.3 |];
  [| 93.8 ; 25.9 |];
  [| 91.6 ; 9.1 |];
  [| 63.4 ; 63.0 |];
  [| 81.9 ; 1.9 |];
  [| 48.0 ; 44.5 |];
  [| 85.3 ; 58.6 |];
  [| 59.3 ; 11.0 |];
  [| 84.6 ; 26.5 |];
  [| 41.4 ; 11.2 |];
  [| 34.8 ; 44.6 |];
  [| 15.1 ; 56.0 |];
  [| 33.8 ; 54.4 |];
  [| 10.7 ; 63.3 |];
  [| 63.8 ; 18.7 |];
  [| 42.2 ; 38.7 |];
  [| 46.0 ; 12.5 |];
  [| 57.2 ; 32.6 |];
  [| 58.6 ; 14.0 |];
  [| 37.6 ; 49.8 |];
  [| 93.5 ; 47.1 |];
  [| 2.5 ; 6.0 |];
  [| 63.1 ; 8.2 |];
  [| 44.6 ; 44.3 |];
  [| 72.6 ; 42.9 |];
  [| 22.8 ; 36.6 |];
  [| 79.1 ; 33.5 |];
  [| 90.6 ; 16.6 |];
  [| 60.6 ; 45.9 |];
  [| 71.8 ; 53.3 |];
  [| 66.8 ; 29.3 |];
  [| 33.6 ; 46.0 |];
  [| 36.3 ; 17.9 |];
  [| 86.0 ; 35.9 |];
  [| 20.9 ; 46.3 |];
  [| 35.3 ; 4.6 |];
  [| 47.4 ; 31.7 |];
  [| 75.6 ; 1.6 |];
  [| 1.7 ; 21.3 |];
  [| 63.2 ; 31.1 |];
  [| 78.2 ; 62.3 |];
  [| 28.5 ; 18.5 |];
  [| 35.0 ; 33.0 |];
  [| 80.2 ; 53.7 |];
  [| 35.1 ; 42.7 |];
  [| 10.2 ; 31.8 |];
  [| 66.5 ; 33.6 |];
  [| 45.9 ; 64.5 |];
  [| 32.7 ; 28.5 |];
  [| 89.8 ; 30.2 |];
  [| 79.1 ; 11.8 |];
  [| 72.6 ; 55.1 |];
  [| 4.8 ; 24.3 |];
  [| 36.4 ; 15.0 |];
  [| 93.5 ; 40.6 |];
  [| 18.7 ; 42.6 |];
  [| 40.8 ; 28.7 |];
  [| 79.2 ; 50.3 |];
  [| 7.0 ; 18.1 |];
  [| 38.7 ; 8.3 |];
  [| 55.5 ; 11.0 |];
  [| 52.8 ; 52.6 |];
  [| 8.5 ; 19.1 |];
  [| 56.7 ; 48.9 |];
  [| 74.5 ; 3.8 |];
  [| 44.7 ; 38.0 |];
  [| 25.9 ; 3.8 |];
  [| 1.7 ; 34.6 |];
  [| 73.3 ; 8.1 |];
  [| 58.5 ; 62.5 |];
  [| 60.2 ; 47.3 |];
  [| 4.3 ; 11.8 |];
  [| 30.6 ; 41.9 |];
  [| 63.8 ; 37.6 |];
  [| 64.2 ; 60.3 |];
  [| 14.9 ; 53.7 |];
  [| 63.9 ; 22.2 |];
  [| 29.7 ; 42.0 |];
  [| 72.1 ; 24.0 |];
  [| 29.1 ; 64.3 |];
  [| 28.0 ; 21.6 |];
  [| 29.5 ; 22.6 |];
  [| 81.0 ; 29.7 |];
  [| 85.4 ; 41.6 |];
  [| 57.4 ; 38.6 |];
  [| 43.0 ; 25.1 |];
  [| 20.7 ; 21.3 |];
  [| 80.2 ; 33.5 |];
  [| 60.8 ; 5.0 |];
  [| 94.1 ; 2.5 |];
  [| 32.6 ; 24.7 |];
  [| 14.2 ; 32.6 |];
  [| 66.6 ; 56.6 |];
  [| 29.8 ; 36.9 |];
  [| 0.7 ; 57.1 |];
  [| 92.7 ; 63.1 |];
  [| 60.7 ; 41.1 |];
  [| 33.7 ; 30.2 |];
  [| 91.5 ; 24.1 |];
  [| 14.2 ; 21.7 |];
  [| 44.2 ; 31.0 |];
  [| 94.9 ; 57.4 |];
  [| 44.7 ; 42.3 |];
  [| 58.7 ; 12.2 |];
  [| 82.7 ; 3.7 |];
  [| 83.0 ; 50.4 |];
  [| 8.4 ; 35.6 |];
  [| 53.4 ; 9.9 |];
  [| 39.0 ; 22.2 |];
  [| 60.0 ; 24.2 |];
  [| 0.9 ; 22.2 |];
  [| 73.9 ; 52.1 |];
  [| 50.1 ; 21.5 |];
  [| 8.8 ; 8.0 |];
  [| 66.5 ; 28.1 |];
  [| 81.1 ; 17.0 |];
  [| 12.4 ; 35.7 |];
  [| 81.0 ; 25.4 |];
  [| 86.3 ; 12.1 |];
  [| 4.8 ; 4.5 |];
  [| 77.0 ; 60.7 |];
  [| 78.8 ; 16.8 |];
  [| 6.3 ; 50.3 |];
  [| 90.5 ; 19.6 |];
  [| 56.9 ; 16.3 |];
  [| 90.3 ; 47.3 |];
  [| 4.8 ; 50.2 |];
  [| 16.8 ; 38.4 |];
  [| 68.7 ; 42.5 |];
  [| 47.8 ; 58.5 |];
  [| 37.7 ; 33.5 |];
  [| 69.1 ; 47.9 |];
  [| 73.6 ; 17.1 |];
  [| 57.4 ; 11.2 |];
  [| 14.4 ; 4.2 |];
  [| 86.8 ; 7.0 |];
  [| 71.3 ; 31.2 |];
  [| 44.5 ; 64.8 |];
  [| 26.7 ; 3.3 |];
  [| 16.7 ; 36.9 |];
  [| 34.0 ; 44.8 |];
  [| 1.6 ; 24.3 |];
  [| 89.9 ; 37.7 |];
  [| 55.5 ; 14.3 |];
  [| 44.0 ; 6.8 |];
  [| 58.7 ; 19.7 |];
  [| 85.8 ; 35.9 |];
  [| 13.1 ; 1.7 |];
  [| 30.7 ; 57.5 |];
  [| 59.0 ; 64.5 |];
  [| 59.1 ; 42.0 |];
  [| 75.9 ; 45.4 |];
  [| 83.7 ; 64.3 |];
  [| 25.8 ; 3.8 |];
  [| 35.4 ; 35.4 |];
  [| 31.8 ; 24.3 |];
  [| 37.2 ; 8.6 |];
  [| 13.3 ; 57.7 |];
  [| 18.5 ; 32.1 |];
  [| 52.7 ; 21.7 |];
  [| 42.9 ; 26.4 |];
  [| 90.9 ; 35.6 |];
  [| 60.8 ; 30.4 |];
  [| 33.9 ; 28.6 |];
  [| 35.6 ; 27.4 |];
  [| 59.9 ; 14.0 |];
  [| 28.8 ; 29.4 |];
  [| 79.6 ; 1.6 |];
  [| 18.7 ; 58.6 |];
  [| 75.1 ; 22.2 |];
  [| 70.4 ; 59.1 |];
  [| 76.9 ; 44.0 |];
  [| 51.9 ; 14.1 |];
  [| 88.3 ; 58.9 |];
  [| 44.0 ; 27.0 |];
  [| 69.8 ; 8.7 |];
  [| 24.2 ; 44.1 |];
  [| 23.2 ; 15.2 |];
  [| 21.6 ; 32.5 |];
  [| 56.9 ; 52.4 |];
  [| 47.0 ; 28.0 |];
  [| 90.2 ; 32.9 |];
  [| 64.2 ; 32.0 |];
  [| 51.5 ; 3.8 |];
  [| 38.7 ; 12.7 |];
  [| 91.5 ; 29.3 |];
  [| 12.6 ; 40.6 |];
  [| 62.2 ; 35.8 |];
  [| 68.1 ; 38.9 |];
  [| 9.4 ; 49.5 |];
  [| 63.2 ; 14.1 |];
  [| 79.7 ; 7.7 |];
  [| 34.9 ; 60.0 |];
  [| 15.5 ; 26.2 |];
  [| 80.4 ; 28.1 |];
  [| 53.7 ; 35.8 |];
  [| 22.1 ; 5.6 |];
  [| 11.6 ; 43.8 |];
  [| 1.2 ; 59.2 |];
  [| 68.4 ; 34.7 |];
  [| 69.2 ; 64.1 |];
  [| 1.8 ; 32.1 |];
  [| 90.5 ; 1.0 |];
  [| 49.9 ; 8.0 |];
  [| 19.6 ; 48.5 |];
  [| 20.9 ; 38.1 |];
  [| 82.8 ; 46.4 |];
  [| 47.7 ; 17.1 |];
  [| 82.8 ; 18.6 |];
  [| 86.8 ; 41.5 |];
  [| 20.4 ; 48.0 |];
  [| 42.8 ; 35.0 |];
  [| 1.3 ; 61.4 |];
  [| 20.7 ; 60.2 |];
  [| 82.2 ; 23.1 |];
  [| 57.3 ; 53.2 |];
  [| 13.2 ; 3.6 |];
  [| 65.7 ; 33.5 |];
  [| 39.8 ; 20.3 |];
  [| 94.7 ; 24.2 |];
  [| 21.4 ; 29.7 |];
  [| 84.6 ; 62.4 |];
  [| 42.8 ; 39.7 |];
  [| 23.3 ; 9.9 |];
  [| 33.6 ; 10.2 |];
  [| 75.8 ; 63.5 |];
  [| 42.5 ; 44.1 |];
  [| 11.4 ; 1.9 |];
  [| 56.9 ; 0.9 |];
  [| 42.0 ; 22.1 |];
  [| 44.1 ; 34.6 |];
  [| 81.6 ; 24.3 |];
  [| 90.8 ; 47.9 |];
  [| 82.4 ; 13.3 |];
  [| 41.7 ; 64.5 |];
  [| 31.6 ; 7.3 |];
  [| 3.1 ; 24.6 |];
  [| 4.0 ; 48.9 |];
  [| 86.1 ; 3.1 |];
  [| 86.5 ; 23.1 |];
  [| 33.7 ; 5.7 |];
  [| 89.8 ; 1.7 |];
  [| 52.7 ; 55.9 |];
  [| 4.8 ; 19.0 |];
  [| 32.9 ; 35.3 |];
  [| 58.6 ; 52.5 |];
  [| 75.3 ; 61.2 |];
  [| 45.7 ; 35.1 |];
  [| 64.7 ; 1.6 |];
  [| 8.8 ; 40.6 |];
  [| 54.7 ; 63.4 |];
  [| 55.9 ; 52.8 |];
  [| 0.7 ; 34.5 |];
  [| 66.0 ; 34.7 |];
  [| 56.7 ; 6.4 |];
  [| 80.8 ; 46.1 |];
  [| 91.0 ; 30.7 |];
  [| 12.5 ; 57.0 |];
  [| 20.6 ; 23.9 |];
  [| 50.8 ; 5.6 |];
  [| 43.9 ; 44.1 |];
  [| 63.4 ; 63.9 |];
  [| 21.0 ; 42.3 |];
  [| 10.5 ; 16.6 |];
  [| 13.4 ; 30.4 |];
  [| 29.8 ; 55.7 |];
  [| 39.6 ; 14.2 |];
  [| 65.6 ; 11.4 |];
  [| 93.3 ; 51.3 |];
  [| 22.2 ; 12.5 |];
  [| 74.4 ; 34.3 |];
  [| 37.6 ; 3.8 |];
  [| 72.9 ; 60.5 |];
  [| 25.0 ; 37.6 |];
  [| 58.7 ; 15.6 |];
  [| 55.3 ; 9.5 |];
  [| 68.8 ; 33.1 |];
  [| 39.0 ; 38.6 |];
  [| 45.1 ; 15.7 |];
  [| 42.3 ; 50.7 |];
  [| 35.2 ; 7.7 |];
  [| 86.9 ; 3.3 |];
  [| 83.6 ; 41.3 |];
  [| 34.7 ; 63.0 |];
  [| 39.4 ; 3.2 |];
  [| 79.6 ; 56.0 |];
  [| 71.9 ; 1.4 |];
  [| 82.7 ; 57.7 |];
  [| 18.4 ; 48.2 |];
  [| 72.2 ; 55.0 |];
  [| 70.4 ; 32.7 |];
  [| 84.5 ; 49.5 |];
  [| 20.0 ; 54.9 |];
  [| 35.3 ; 23.2 |];
  [| 90.7 ; 16.2 |];
  [| 47.9 ; 17.8 |];
  [| 35.0 ; 54.0 |];
  [| 59.9 ; 5.5 |];
  [| 79.6 ; 64.1 |];
  [| 32.0 ; 32.2 |];
  [| 50.1 ; 24.0 |];
  [| 33.1 ; 1.0 |];
  [| 68.9 ; 58.5 |];
  [| 82.0 ; 26.8 |];
  [| 56.0 ; 19.3 |];
  [| 46.5 ; 57.5 |];
  [| 12.9 ; 60.7 |];
  [| 30.8 ; 15.2 |];
  [| 39.6 ; 27.8 |];
  [| 46.1 ; 12.4 |];
  [| 80.9 ; 1.6 |];
  [| 16.4 ; 40.3 |];
  [| 59.9 ; 25.4 |];
  [| 26.9 ; 53.1 |];
  [| 0.5 ; 62.3 |];
  [| 95.0 ; 8.4 |];
  [| 45.9 ; 65.0 |];
  [| 87.6 ; 62.9 |];
  [| 17.2 ; 49.2 |];
  [| 45.0 ; 62.5 |];
  [| 29.0 ; 44.0 |];
  [| 19.5 ; 11.5 |];
  [| 93.1 ; 14.3 |];
  [| 21.9 ; 62.2 |];
  [| 2.5 ; 46.3 |];
  [| 62.7 ; 57.4 |];
  [| 0.6 ; 64.8 |];
  [| 58.3 ; 56.4 |];
  [| 52.7 ; 65.0 |];
  [| 62.4 ; 43.7 |];
  [| 42.5 ; 7.8 |];
  [| 87.9 ; 63.2 |];
  [| 73.2 ; 24.7 |];
  [| 93.8 ; 21.9 |];
  [| 1.5 ; 31.6 |];
  [| 17.3 ; 31.2 |];
  [| 88.7 ; 61.4 |];
  [| 48.3 ; 61.8 |];
  [| 5.2 ; 37.1 |];
  [| 32.1 ; 7.3 |];
  [| 22.0 ; 49.4 |];
  [| 34.6 ; 29.1 |];
  [| 84.8 ; 60.8 |];
  [| 34.6 ; 28.1 |];
  [| 11.9 ; 31.8 |];
  [| 93.5 ; 41.0 |];
  [| 54.9 ; 61.6 |];
  [| 16.6 ; 63.1 |];
  [| 20.2 ; 22.9 |];
  [| 35.5 ; 36.5 |];
  [| 47.4 ; 63.2 |];
  [| 22.6 ; 38.2 |];
  [| 73.5 ; 23.4 |];
  [| 57.9 ; 37.2 |];
  [| 71.2 ; 28.8 |];
  [| 56.6 ; 60.1 |];
  [| 0.7 ; 23.2 |];
  [| 58.0 ; 58.9 |];
  [| 8.9 ; 8.7 |];
  [| 68.8 ; 36.9 |];
  [| 57.2 ; 44.0 |];
  [| 5.0 ; 41.1 |];
  [| 29.3 ; 11.3 |];
  [| 15.7 ; 43.6 |];
  [| 85.9 ; 7.1 |];
  [| 51.5 ; 16.2 |];
  [| 80.0 ; 39.6 |];
  [| 73.2 ; 11.5 |];
  [| 22.4 ; 35.2 |];
  [| 27.2 ; 33.5 |];
  [| 36.1 ; 23.6 |];
  [| 19.4 ; 57.4 |];
  [| 43.1 ; 13.3 |];
  [| 13.2 ; 19.2 |];
  [| 45.3 ; 2.4 |];
  [| 67.4 ; 30.7 |];
  [| 38.3 ; 47.1 |];
  [| 13.1 ; 32.3 |];
  [| 86.8 ; 42.1 |];
  [| 14.1 ; 48.8 |];
  [| 75.8 ; 42.1 |];
  [| 64.7 ; 27.6 |];
  [| 61.9 ; 41.3 |];
  [| 8.4 ; 15.8 |];
  [| 36.2 ; 32.6 |];
  [| 48.6 ; 51.6 |];
  [| 1.7 ; 16.8 |];
  [| 13.3 ; 9.6 |];
  [| 6.2 ; 22.7 |];
  [| 39.3 ; 64.1 |];
  [| 81.3 ; 40.6 |];
  [| 34.2 ; 44.3 |];
  [| 31.6 ; 7.0 |];
  [| 29.5 ; 42.7 |];
  [| 29.0 ; 52.5 |];
  [| 27.1 ; 38.5 |];
  [| 48.2 ; 6.0 |];
  [| 57.9 ; 62.9 |];
  [| 51.2 ; 49.6 |];
  [| 16.5 ; 36.1 |];
  [| 55.4 ; 30.4 |];
  [| 4.6 ; 47.6 |];
  [| 87.7 ; 56.1 |];
  [| 69.3 ; 31.4 |];
  [| 89.8 ; 10.2 |];
  [| 72.0 ; 31.8 |];
  [| 80.1 ; 43.9 |];
  [| 57.3 ; 56.3 |];
  [| 40.2 ; 62.4 |];
  [| 86.1 ; 42.4 |];
  [| 46.7 ; 41.4 |];
  [| 11.4 ; 1.1 |];
  [| 63.5 ; 52.1 |];
  [| 83.2 ; 26.0 |];
  [| 29.2 ; 22.2 |];
  [| 36.7 ; 60.0 |];
  [| 52.2 ; 55.0 |];
  [| 88.4 ; 54.2 |];
  [| 15.0 ; 0.9 |];
  [| 41.0 ; 40.4 |];
  [| 51.3 ; 35.5 |];
  [| 73.0 ; 20.2 |];
  [| 50.5 ; 37.9 |];
  [| 55.6 ; 21.7 |];
  [| 38.5 ; 54.8 |];
  [| 41.3 ; 3.9 |];
  [| 85.0 ; 64.5 |];
  [| 3.4 ; 52.8 |];
  [| 28.4 ; 0.6 |];
  [| 28.0 ; 7.4 |];
  [| 79.9 ; 5.5 |];
  [| 84.3 ; 61.0 |];
  [| 3.5 ; 34.9 |];
  [| 23.5 ; 19.6 |];
  [| 46.8 ; 22.3 |];
  [| 38.3 ; 54.9 |];
  [| 4.4 ; 37.7 |];
  [| 42.3 ; 0.9 |];
  [| 66.9 ; 4.5 |];
  [| 78.4 ; 4.9 |];
  [| 15.6 ; 18.3 |];
  [| 29.6 ; 44.6 |];
  [| 58.6 ; 36.0 |];
  [| 37.2 ; 53.6 |];
  [| 7.8 ; 60.9 |];
  [| 54.5 ; 56.4 |];
  [| 7.8 ; 23.5 |];
  [| 36.0 ; 7.6 |];
  [| 54.3 ; 51.7 |];
  [| 1.6 ; 64.5 |];
  [| 14.4 ; 2.3 |];
  [| 12.1 ; 40.2 |];
  [| 48.7 ; 38.4 |];
  [| 59.4 ; 23.7 |];
  [| 78.4 ; 8.2 |];
  [| 54.8 ; 19.0 |];
  [| 38.0 ; 57.9 |];
  [| 30.0 ; 12.5 |];
  [| 33.2 ; 21.6 |];
  [| 82.1 ; 50.2 |];
  [| 13.7 ; 26.4 |];
  [| 21.7 ; 9.8 |];
  [| 27.4 ; 63.1 |];
  [| 94.4 ; 35.1 |];
  [| 2.3 ; 18.1 |];
  [| 85.3 ; 34.6 |];
  [| 37.4 ; 17.5 |];
  [| 90.2 ; 62.2 |];
  [| 55.9 ; 44.7 |];
  [| 41.7 ; 12.2 |];
  [| 9.9 ; 10.8 |];
  [| 24.3 ; 59.3 |];
  [| 17.4 ; 49.7 |];
  [| 21.9 ; 49.2 |];
  [| 94.6 ; 28.7 |];
  [| 46.0 ; 22.0 |];
  [| 67.4 ; 41.9 |];
  [| 22.8 ; 46.3 |];
  [| 24.9 ; 49.5 |];
  [| 57.9 ; 63.4 |];
  [| 29.6 ; 3.3 |];
  [| 48.7 ; 25.1 |];
  [| 37.8 ; 19.2 |];
  [| 20.7 ; 52.0 |];
  [| 25.6 ; 60.7 |];
  [| 44.4 ; 28.6 |];
  [| 30.2 ; 49.9 |];
  [| 15.8 ; 43.6 |];
  [| 21.8 ; 48.4 |];
  [| 42.8 ; 36.1 |];
  [| 58.3 ; 58.7 |];
  [| 15.5 ; 44.6 |];
  [| 69.0 ; 30.2 |];
  [| 94.7 ; 17.9 |];
  [| 89.6 ; 21.1 |];
  [| 37.0 ; 45.0 |];
  [| 12.9 ; 23.3 |];
  [| 55.6 ; 28.5 |];
  [| 41.0 ; 4.1 |];
  [| 36.0 ; 24.5 |];
  [| 71.7 ; 26.6 |];
  [| 76.9 ; 13.9 |];
  [| 31.7 ; 3.8 |];
  [| 68.8 ; 53.3 |];
  [| 78.8 ; 8.4 |];
  [| 4.8 ; 32.0 |];
  [| 14.7 ; 56.5 |];
  [| 55.7 ; 55.4 |];
  [| 85.7 ; 33.7 |];
  [| 54.6 ; 44.5 |];
  [| 94.8 ; 10.4 |];
  [| 29.8 ; 8.0 |];
  [| 5.6 ; 45.8 |];
  [| 39.6 ; 28.6 |];
  [| 6.6 ; 18.5 |];
  [| 14.0 ; 3.5 |];
  [| 79.1 ; 55.8 |];
  [| 82.9 ; 53.5 |];
  [| 30.6 ; 53.7 |];
  [| 89.5 ; 10.4 |];
  [| 59.2 ; 56.8 |];
  [| 2.0 ; 41.7 |];
  [| 2.8 ; 58.5 |];
  [| 42.8 ; 17.5 |];
  [| 50.5 ; 55.5 |];
  [| 71.5 ; 1.3 |];
  [| 65.1 ; 21.8 |];
  [| 40.6 ; 60.9 |];
  [| 44.6 ; 13.7 |];
  [| 84.5 ; 64.5 |];
  [| 18.4 ; 62.5 |];
  [| 21.1 ; 32.2 |];
  [| 48.1 ; 57.2 |];
  [| 39.8 ; 15.8 |];
  [| 34.0 ; 2.2 |];
  [| 73.7 ; 19.3 |];
  [| 72.2 ; 24.4 |];
  [| 47.4 ; 10.1 |];
  [| 13.2 ; 36.9 |];
  [| 76.7 ; 8.0 |];
  [| 36.6 ; 28.3 |];
  [| 49.5 ; 35.5 |];
  [| 77.0 ; 49.7 |];
  [| 28.7 ; 62.2 |];
  [| 9.7 ; 37.9 |];
  [| 72.8 ; 10.3 |];
  [| 15.2 ; 47.3 |];
  [| 35.9 ; 37.0 |];
  [| 20.5 ; 46.6 |];
  [| 71.2 ; 35.2 |];
  [| 10.0 ; 64.9 |];
  [| 87.4 ; 27.3 |];
  [| 33.0 ; 54.2 |];
  [| 86.8 ; 26.1 |];
  [| 75.8 ; 23.1 |];
  [| 32.8 ; 57.1 |];
  [| 90.3 ; 0.8 |];
  [| 40.4 ; 5.6 |];
  [| 92.3 ; 26.7 |];
  [| 77.4 ; 40.5 |];
  [| 42.6 ; 46.1 |];
  [| 34.2 ; 45.5 |];
  [| 26.2 ; 59.2 |];
  [| 35.5 ; 57.6 |];
  [| 40.0 ; 38.6 |];
  [| 75.2 ; 30.8 |];
  [| 57.0 ; 40.5 |];
  [| 19.0 ; 50.0 |];
  [| 26.1 ; 62.4 |];
  [| 53.3 ; 0.9 |];
  [| 28.1 ; 19.6 |];
  [| 83.5 ; 53.0 |];
  [| 27.5 ; 42.5 |];
  [| 69.6 ; 18.6 |];
  [| 78.9 ; 8.9 |];
  [| 82.8 ; 32.2 |];
  [| 93.9 ; 37.8 |];
  [| 88.5 ; 53.8 |];
  [| 71.2 ; 39.8 |];
  [| 67.5 ; 2.5 |];
  [| 92.2 ; 36.9 |];
  [| 38.8 ; 22.8 |];
  [| 56.1 ; 15.8 |];
  [| 52.9 ; 52.8 |];
  [| 91.1 ; 1.2 |];
  [| 51.3 ; 0.7 |];
  [| 36.6 ; 35.1 |];
  [| 18.1 ; 36.8 |];
  [| 20.2 ; 56.3 |];
  [| 74.2 ; 26.3 |];
  [| 79.1 ; 7.6 |];
  [| 52.4 ; 6.3 |];
  [| 85.9 ; 7.8 |];
  [| 0.5 ; 37.8 |];
  [| 9.5 ; 32.4 |];
  [| 30.3 ; 43.3 |];
  [| 24.6 ; 28.2 |];
  [| 41.8 ; 56.6 |];
  [| 19.6 ; 31.0 |];
  [| 79.3 ; 0.9 |];
  [| 78.9 ; 40.6 |];
  [| 25.0 ; 1.2 |];
  [| 16.8 ; 20.6 |];
  [| 56.3 ; 24.2 |];
  [| 54.3 ; 5.6 |];
  [| 15.3 ; 60.4 |];
  [| 78.0 ; 15.0 |];
  [| 41.1 ; 36.9 |];
  [| 67.4 ; 22.7 |];
  [| 52.8 ; 51.8 |];
  [| 52.2 ; 10.5 |];
  [| 64.5 ; 53.2 |];
  [| 12.1 ; 59.8 |];
  [| 11.0 ; 20.6 |];
  [| 70.4 ; 25.9 |];
  [| 77.5 ; 37.3 |];
  [| 11.3 ; 18.8 |];
  [| 48.7 ; 15.7 |];
  [| 78.8 ; 6.6 |];
  [| 66.7 ; 12.9 |];
  [| 50.9 ; 21.7 |];
  [| 22.6 ; 41.3 |];
  [| 21.1 ; 3.9 |];
  [| 26.2 ; 33.1 |];
  [| 49.0 ; 8.6 |];
  [| 35.0 ; 30.1 |];
  [| 50.9 ; 52.2 |];
  [| 51.4 ; 30.5 |];
  [| 71.2 ; 46.7 |];
  [| 71.3 ; 40.4 |];
  [| 81.9 ; 55.1 |];
  [| 9.1 ; 25.5 |];
  [| 33.0 ; 31.6 |];
  [| 27.8 ; 53.4 |];
  [| 34.3 ; 8.6 |];
  [| 43.1 ; 15.5 |];
  [| 86.3 ; 32.4 |];
  [| 82.2 ; 63.2 |];
  [| 29.4 ; 6.9 |];
  [| 6.4 ; 29.3 |];
  [| 15.0 ; 39.7 |];
  [| 53.5 ; 35.8 |];
  [| 7.3 ; 48.3 |];
  [| 48.9 ; 7.5 |];
  [| 66.5 ; 36.8 |];
  [| 74.8 ; 36.7 |];
  [| 47.0 ; 63.9 |];
  [| 39.9 ; 57.9 |];
  [| 70.1 ; 32.6 |];
  [| 57.1 ; 37.2 |];
  [| 69.8 ; 16.2 |];
  [| 63.1 ; 50.4 |];
  [| 9.7 ; 46.4 |];
  [| 76.8 ; 60.6 |];
  [| 79.7 ; 9.7 |];
  [| 49.3 ; 10.8 |];
  [| 30.7 ; 54.5 |];
  [| 49.0 ; 57.6 |];
  [| 14.4 ; 47.1 |];
  [| 75.6 ; 37.3 |];
  [| 93.3 ; 49.2 |];
  [| 59.3 ; 44.8 |];
  [| 79.2 ; 22.3 |];
  [| 81.7 ; 42.0 |];
  [| 20.8 ; 53.5 |];
  [| 27.0 ; 25.7 |];
  [| 21.4 ; 5.0 |];
  [| 23.7 ; 0.9 |];
  [| 16.1 ; 37.2 |];
  [| 79.2 ; 56.3 |];
  [| 75.2 ; 17.9 |];
  [| 65.1 ; 36.9 |];
  [| 90.5 ; 49.2 |];
  [| 93.2 ; 1.3 |];
  [| 53.0 ; 40.2 |];
  [| 87.0 ; 11.5 |];
  [| 2.4 ; 40.7 |];
  [| 25.0 ; 49.4 |];
  [| 14.0 ; 37.0 |];
  [| 41.6 ; 24.1 |];
  [| 85.2 ; 61.4 |];
  [| 84.2 ; 38.8 |];
  [| 95.0 ; 36.9 |];
  [| 33.7 ; 22.7 |];
  [| 47.5 ; 14.5 |];
  [| 67.8 ; 26.4 |];
  [| 29.1 ; 18.2 |];
  [| 40.6 ; 35.0 |];
  [| 12.3 ; 9.0 |];
  [| 5.1 ; 1.2 |];
  [| 74.6 ; 18.1 |];
  [| 86.6 ; 44.0 |];
  [| 34.6 ; 27.9 |];
  [| 75.6 ; 64.9 |];
  [| 91.0 ; 14.7 |];
  [| 77.3 ; 43.5 |];
  [| 2.1 ; 59.2 |];
  [| 29.9 ; 19.3 |];
  [| 44.0 ; 43.7 |];
  [| 3.7 ; 41.4 |];
  [| 12.2 ; 51.7 |];
  [| 14.6 ; 21.2 |];
  [| 68.8 ; 44.4 |];
  [| 67.7 ; 55.7 |];
  [| 8.0 ; 9.9 |];
  [| 84.0 ; 9.1 |];
  [| 20.0 ; 61.3 |];
  [| 84.4 ; 11.4 |];
  [| 8.5 ; 41.6 |];
  [| 79.9 ; 26.1 |];
  [| 54.6 ; 35.4 |];
  [| 86.7 ; 16.8 |];
  [| 95.0 ; 46.6 |];
  [| 64.4 ; 56.1 |];
  [| 90.5 ; 54.6 |];
  [| 47.5 ; 24.1 |];
  [| 54.7 ; 8.3 |];
  [| 89.0 ; 33.7 |];
  [| 8.4 ; 49.1 |];
  [| 62.0 ; 61.6 |];
  [| 24.2 ; 28.5 |];
  [| 42.4 ; 0.7 |];
  [| 39.4 ; 48.4 |];
  [| 10.2 ; 24.0 |];
  [| 29.9 ; 51.6 |];
  [| 47.5 ; 64.9 |];
  [| 70.4 ; 2.4 |];
  [| 16.0 ; 26.9 |];
  [| 63.6 ; 1.4 |];
  [| 43.4 ; 27.4 |];
  [| 81.1 ; 25.5 |];
  [| 84.1 ; 12.5 |];
  [| 50.6 ; 58.4 |];
  [| 54.8 ; 48.8 |];
  [| 54.2 ; 62.3 |];
  [| 0.6 ; 39.1 |];
  [| 7.1 ; 24.7 |];
  [| 64.9 ; 19.8 |];
  [| 56.2 ; 62.1 |];
  [| 72.6 ; 45.0 |];
  [| 57.7 ; 54.9 |];
  [| 68.0 ; 24.7 |];
  [| 33.2 ; 38.4 |];
  [| 82.7 ; 30.9 |];
  [| 3.6 ; 35.9 |];
  [| 12.7 ; 18.3 |];
  [| 37.0 ; 21.1 |];
  [| 90.4 ; 3.8 |];
  [| 79.4 ; 19.5 |];
  [| 53.7 ; 16.1 |];
  [| 57.0 ; 26.5 |];
  [| 0.8 ; 34.0 |];
  [| 67.9 ; 2.7 |];
  [| 72.4 ; 8.3 |];
  [| 30.2 ; 10.1 |];
  [| 34.5 ; 4.2 |];
  [| 10.2 ; 21.0 |];
  [| 54.2 ; 56.9 |];
  [| 40.2 ; 19.1 |];
  [| 26.5 ; 18.9 |];
  [| 39.5 ; 1.3 |];
  [| 81.9 ; 12.6 |];
  [| 76.4 ; 32.0 |];
  [| 30.5 ; 30.4 |];
  [| 24.3 ; 41.0 |];
  [| 7.8 ; 44.7 |];
  [| 53.2 ; 7.2 |];
  [| 63.6 ; 12.6 |];
  [| 92.5 ; 47.4 |];
  [| 77.7 ; 27.8 |];
  [| 71.4 ; 58.6 |];
  [| 12.3 ; 37.5 |];
  [| 35.1 ; 62.6 |];
  [| 28.5 ; 14.4 |];
  [| 32.7 ; 62.3 |];
  [| 49.2 ; 6.9 |];
  [| 83.1 ; 25.5 |];
  [| 64.4 ; 46.2 |];
  [| 62.5 ; 45.0 |];
  [| 59.6 ; 28.6 |];
  [| 94.3 ; 40.5 |];
  [| 70.6 ; 21.1 |];
  [| 70.3 ; 40.4 |];
  [| 20.2 ; 59.3 |];
  [| 50.8 ; 45.2 |];
  [| 14.1 ; 35.9 |];
  [| 1.0 ; 51.4 |];
  [| 2.5 ; 34.0 |];
  [| 88.9 ; 25.1 |];
  [| 78.2 ; 61.1 |];
  [| 27.9 ; 1.7 |];
  [| 40.2 ; 14.6 |];
  [| 24.8 ; 54.5 |];
  [| 89.1 ; 17.3 |];
  [| 59.8 ; 47.7 |];
  [| 9.2 ; 55.8 |];
  [| 78.1 ; 64.7 |];
  [| 19.4 ; 8.8 |];
  [| 79.6 ; 12.7 |];
  [| 15.6 ; 47.6 |];
  [| 68.7 ; 57.8 |];
  [| 69.4 ; 63.8 |];
  [| 14.7 ; 58.0 |];
  [| 7.0 ; 17.1 |];
  [| 15.0 ; 53.1 |];
  [| 60.9 ; 35.3 |];
  [| 80.4 ; 38.9 |];
  [| 10.9 ; 22.7 |];
  [| 93.6 ; 40.8 |];
  [| 75.0 ; 32.2 |];
  [| 23.7 ; 43.9 |];
  [| 68.1 ; 60.9 |];
  [| 90.5 ; 3.1 |];
  [| 10.8 ; 50.2 |];
  [| 9.9 ; 27.6 |];
  [| 3.5 ; 11.2 |];
  |];;

let rec inserer tree pt p =
  (* inserer dans l'abre le point pt, sachant qu'on est à la profondeur p *) 
  match tree with
  | V -> N (V, pt, V)
  | N (ag, v, ad) -> 
    if pt.(p mod d) <= v.(p mod d) then N (inserer ag pt (p+1), v, ad)
    else N (ag, v, inserer ad pt (p+1))

let construire data =
  (* construction du kdtree *)
  let tree = ref V in
  for i = 0 to Array.length data - 1 do
    tree := inserer !tree data.(i) 0
  done;
  !tree
;;

(* distance entre deux points *)
let dist pt1 pt2 = 
  let n = Array.length pt1 in
  let n2 = Array.length pt2 in
  assert (n = n2);
  let s = ref 0. in
  for i = 0 to (n - 1) do
    s := !s +. (pt1.(i) -. pt2.(i)) ** 2.
  done;
  sqrt !s;;


(* structure de données pour stocker les k meilleurs *)

type k_meilleurs = { nmax : int; mutable nb : int; mutable voisins : (float array * float * int) list}
(* nmax : nombre maximal de point à conserver *)
(* nb : nombre de points conservés *)
(* voisins : liste des points conservés, triés par distance décroissante, accompagné de leur classe *)

let creerKM k = { nmax = k; nb = 0; voisins = [] };;

let ajouterKM km (pt,dist,c) =
  let rec inserer (pt, dist, c) l = match l with
  | [] -> [(pt, dist, c)]
  | (pt2, dist2, c2) :: ll -> if dist < dist2 then (pt2, dist2, c2) :: (inserer (pt, dist, c) ll) else (pt, dist, c) :: l
  in
  if km.nb < km.nmax then begin (* il reste de la place ! *)
    km.voisins <- inserer (pt, dist, c) km.voisins;
    km.nb <- km.nb + 1
  end else (* c'est plein ! *)
    (* faut-il garder le point ? qui prend alors la place de la tête de liste *)
    let _,dmax,_ = List.hd km.voisins in
    if dist <= dmax then
      km.voisins <- inserer (pt, dist,c) (List.tl km.voisins)
;;


let rayonKM km =
  if (km.nb < km.nmax) then infinity else let _,dmax,_ = List.hd km.voisins in dmax;;

let k_plus_proches_voisins k tree pt =
  let km = creerKM k in (* les k points les plus proches rencontrés *)
  let nbcomp = ref 0 in (* compteur du nombre de comparaisons *)

  (* parcours intelligent de l'arbre en gardant en mémoire les k points les plus proches *)
  let rec parcours t p = 
    match t with
    | V -> ()
    | N (ag, v, ad) -> 
      (* ordre de visite : quel est le premier sous arbre à visiter ? *)
      let (a1, a2) = if pt.(p mod d) <= v.(p mod d) then (ag, ad) else (ad, ag)
      in
        parcours a1 (p + 1);
        (* est-ce nécessaire de visiter le 2e sous arbre ? *)
        let r = rayonKM km in
        if (r > abs_float (pt.(p mod d) -. v.(p mod d))) then begin
          (* on tient compte du point séparateur, et du 2e sous-arbre *)
          nbcomp := !nbcomp + 1;
          ajouterKM km (v, dist pt v, 0) ; parcours a2 (p + 1)
        end (* else : sous-arbre non exploré *)
  in
  parcours tree 0; Printf.printf "Nb total de points considérés = %d\n" !nbcomp; List.map (fun (x,y,z) -> x) km.voisins
;;

(* test *)
let bigtree = construire pt_test in
let kpppt = k_plus_proches_voisins 5 bigtree [|30.5;56.3|] in
List.iter (fun pt -> Printf.printf "pt : %f,%f\n" pt.(0) pt.(1)) kpppt;;