Площадь с минимальной площадью, охватывающей K баллов среди заданных N баллов

Этот вопрос задавали мне в онлайн-тесте. В карте декартовой плоскости имеется N точек. Будет задано целое число K. Цель состоит в том, чтобы найти площадь квадрата (минимум), вмещающую не менее K точек. Стороны квадрата должны быть параллельны оси. Вершины квадрата должны быть целыми числами. Любые точки, лежащие по бокам, не считаются внутри квадрата.Площадь с минимальной площадью, охватывающей K баллов среди заданных N баллов

Я мог бы решить его только для 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 точек и описанной выше методики для всех комбинаций, но это не является хорошим. Пожалуйста, порекомендуйте.

источник

2015-06-20 Ouney

Вы можете взять статистический подход и вычислить стандартное отклонение каждой из точек вдоль х и ось y, затем удалите первые N-K-точки с самым высоким стандартным отклонением. –

Вам нужно найти квадрат, охватывающий не менее 'K' точек или точно' K' точек? –

Я действительно не помню вопроса, но это должно быть как минимум. Изменит и вопрос. – Ouney

Можно видеть, что мы всегда можем перемещать квадрат так, чтобы он имел точки на левом и нижнем краях. Мы будем перебирать все комбинации левого и нижнего краев квадрата. Тогда нам нужно будет найти верхний или правый край квадрата. Для каждой точки мы можем определить, на каком краю она будет лежать. Например, если 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

источник

2015-06-20 09:47:03

static void initBounds(int[] x, int[] y) 
    { 
     minX = x[0]; 
     maxX = x[0]; 
     minY = y[0]; 
     maxY = y[0]; 
     for(int i = 1; i < x.length; i++){ 
      if(x[i] > maxX) 
       maxX = x[i]; 
      if(x[i] < minX) 
       minX = x[i]; 
      if(y[i] > maxY) 
       maxY = y[i]; 
      if(y[i] < minY) 
       minY = y[i]; 
     } 
    } 

    static int countEnclosingPoints(int[] x, int[] y, int sx1, int sy1, int sx2, int sy2) 
    { 
     int count = 0; 
     for(int i = 0; i < x.length; i++) 
     { 
      if(x[i] > sx1 && x[i] < sx2 && y[i] > sy1 && y[i] < sy2) 
       count++; 
     } 
     return count; 
    } 

    static int minX; 
    static int minY; 
    static int maxX; 
    static int maxY; 

    static long minarea(int[] x, int[] y, int k) { 
     long area = 0; 
     initBounds(x, y); 
     int xDiff = maxX - minX; 
     int yDiff = maxY - minY; 

     int sx1 = minX - 1; 
     int sy1 = minY - 1; 

     int sideDiff = Math.abs(xDiff - yDiff) + 1; 

     int sx2; 
     int sy2; 

     if(xDiff > yDiff){ 
      sx2 = maxX + 1; 
      sy2 = maxY + sideDiff; 
     } else { 
      sx2 = maxX + sideDiff; 
      sy2 = maxY + 1; 
     } 
     area = (sx2 - sx1) * (sx2 - sx1); 

     int p, q, r, s; 
     int minSize = (int) Math.sqrt(k) + 1; 
     for(p = sx1; p < sx2 - minSize; p++) { 
      for(q = sy1; q < sy2 - minSize; q++) { 
       int xd = sx2 - p; int yd = sy2 - q; 
       int sd = (xd < yd)? xd : yd; 
       for(int i = sd; i >= minSize; i--){ 
        int count = countEnclosingPoints(x, y, p, q, p + i, q + i); 
        if(count >= k) { 
         long currArea = i * i; 
         if(currArea < area) 
          area = currArea; 
        } 
        else 
         break; 
       } 
      } 
     } 
     return area; 
    }

Формирует все возможные квадраты с областью (SQRT (к)) * (SQRT (к)) до максимальной ограничивающей площади всех точек. Нижняя левая точка квадрата может находиться где угодно в пределах ограничивающего квадрата. Рассматриваются ограничения, такие как минимальный размер квадрата, необходимый для размещения не менее k точек (sqrt (k)). Если квадрат содержит не менее k точек и площадь меньше текущей области мин, тогда обновите область.

источник

2015-12-07 16:42:01

Похоже, что есть статья Michiel Smid об этой проблеме:

http://pubman.mpdl.mpg.de/pubman/item/escidoc:1834660:2/component/escidoc:1857755/MPI-I-93-116.pdf

представлен алгоритм, который, учитывая набор из п точек на плоскости и целое к, 2 ≤ k ≤ n, находит k точек с наименьшей охватывающей осью-параллельной площадью . Алгоритм имеет время работы O (n log n + kn log2 k) и использует пространство O (n) . Ранее самый известный алгоритм для этой задачи занимает O (K 2n журнала п) время и использует O (кп) пространство

источник

2017-04-14 09:23:42

Площадь с минимальной площадью, охватывающей K баллов среди заданных N баллов

ответ

Смежные вопросы