Квадрат минимальной площади, охватывающий K точек среди заданных N точек ⇐ JAVA

[Anonymous]

Этот вопрос мне задали во время онлайн-теста.
На декартовой плоскости задано 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;

}

Одним из подходов к общему решению было бы найти все возможные комбинации K точек среди N точек и применить описанный выше метод для всех комбинаций, но это нехорошо. Посоветуйте пожалуйста.

Подробнее здесь: https://stackoverflow.com/questions/309 ... n-n-points