最も近いポイントのペア、再帰が正しいエリアで停止していない

Question

ここで最も近いポイントアルゴリズムで作業しています。私はintの2次元配列を取っています。何らかの理由で私は正解を得ていません。 conquerで私の再帰で何が間違っていますか？私はそれが問題だと思う。

package ClosestPair; 

import java.awt.Point; 
import java.util.Arrays; 

public class ClosestPair{ 




public double divide(int[][] data){ 


    int size = data.length; 


    int[][] X_L = new int[size/2][2]; 
    int[][] X_R = new int[size/2][2]; 
    int[][] Y_L = new int[size/2][2]; 
    int[][] Y_R = new int[size/2][2]; 
    int[][] P_L = new int[size][2]; 
    int[][] P_R = new int[size][2]; 






    ////////// X Portion //////////////////////////// 
    //sort the points 
    int[][] temp = data; 
    Arrays.sort(temp, new ColumnComparator(0)); 

    //split the points 
    for (int i = 0; i < temp.length/2; i++){ 
     X_L[i][0] = temp[i][0]; 
     X_L[i][1] = temp[i+1][1]; 
     X_R[i][0] = temp[i+temp.length/2][0]; 
     X_R[i][1] = temp[i+temp.length/2][1]; 
    } 




    ////////// Y Portion //////////////////////////// 
    Arrays.sort(temp, new ColumnComparator(1)); 
      //split the points 
      for (int i = 0; i < temp.length/2; i++){ 
       Y_L[i][0] = temp[i][0]; 
       Y_L[i][1] = temp[i+1][1]; 
       Y_R[i][0] = temp[i+temp.length/2][0]; 
       Y_R[i][1] = temp[i+temp.length/2][1]; 
      } 


      //P_L 
      P_L= appendArrays(X_L, Y_L); 

      //P_R 
      P_R= appendArrays(X_R, Y_R); 

      if(conquer(P_L)< conquer(P_R)) return conquer(P_L); 

      return conquer(P_R);   
} 

public double conquer(int[][] array){ 
    if(array.length == 2){ 
     return distance(array); 
    } 

    int[][] temp1 = new int[array.length/2][2]; 
    int[][] temp2 = new int[array.length/2][2]; 
    int length = array.length/4; 
    for (int i = 0; i < length; i++){ 
     temp1[i][0] = array[i][0]; 
     temp1[i][1] = array[i+1][1]; 
     temp2[i][0] = array[i+array.length/2][0]; 
     temp2[i][1] = array[i+array.length/2][1]; 
    }  
    return conquer(temp1); 
} 


private static int[][] appendArrays(int[][] array1, int[][] array2) { 
     int[][] ret = new int[array1.length + array2.length][]; 
     int i = 0; 
     for (;i<array1.length;i++) { 
      ret[i] = array1[i]; 
     } 
     for (int j = 0;j<array2.length;j++) { 
      ret[i++] = array2[j]; 
     } 
     return ret; 
    } 



public double distance(int[][] points){ 
    //pair distance 
    int a = (points[0][0]+points[1][0]); 
    int b = (points[1][1]+points[1][1]); 
    return Math.sqrt( Math.pow(a, 2) + Math.pow(b, 2) ); 
} 

} 

Answer 1

計算距離が間違っています。それは

int a = (points[0][0]-points[1][0]); 
int b = (points[1][1]-points[1][1]); 
return Math.sqrt( Math.pow(a, 2) + Math.pow(b, 2) ); 

それとも、特殊機能を使用できなければなりません：

int x = (points[0][0]-points[1][0]); 
int y = (points[1][1]-points[1][1]); 
return Math.hypot(x,y); 

を