在给定的N点之间包含K点的最小区域的正方形

Question

这个问题在网上测试中被问到了我.在笛卡尔平面中给出了N个点.将给出整数K. 目的是找到包围至少K点的正方形(最小)区域.正方形的边应平行于轴.正方形的顶点应为整数.位于两侧的任何点都不被视为在广场内.

我只能解决K = N(即所有点都在正方形).

我的解决方案是 -

    static int minarea(int[] x, int[] y, int k) {
    //Find max y
    int maxVal = Integer.MIN_VALUE;
    for(int i : y){
        if(i > maxVal){
            maxVal = i;
        }
    }
    //Find min y
    int minVal = Integer.MAX_VALUE;
    for(int i : x){
        if(i < minVal){
            minVal = i;
        }
    }

    int yLength = (maxVal-minVal)+2;

    //Find max x
    maxVal = Integer.MIN_VALUE;
    for(int i : x){
        if(i > maxVal){
            maxVal = i;
        }
    }
    //Find min x
    minVal = Integer.MAX_VALUE;
    for(int i : x){
        if(i < minVal){
            minVal = i;
        }
    }

    int xLength = (maxVal-minVal)+2;
    int sqSide = (yLength > xLength)?yLength:xLength;
    return sqSide*sqSide;

}

一般解决方案的一种方法是在N个点之间找到K点的所有可能组合,并且对于所有组合应用上述方法但是这不是好的.请指教.

Answer 1

可以看出，我们总是可以移动正方形，使其在左边缘和下边缘都有点。我们将迭代正方形左边缘和下边缘的所有组合。然后我们需要找到正方形的上边缘或右边缘。对于每个点，我们都可以确定它所在的边缘。例如，如果point.x - left > point.y - bottom该点位于正方形的右边缘，则所得面积将为( point.x - left )^2。我们需要按正方形面积对点进行排序：area = ( max( point.x - left, point.y - bottom ) )^2并K从此排序列表中选择第 - 个点。它将是至少包含K具有指定左下角的点的最小正方形。该解决方案的复杂性O(n^3)不是很好，但它比迭代所有K点组合要快。我的java解决方案： https: //ideone.com/139C7A