Conteo de puntos tales que la suma de las distancias de Manhattan se minimiza

Dados N puntos en K espacio dimensional en una array 2D Points[][] , donde 1≤ N ≤ 10 ⁵ y 1 ≤ K ≤ 5 . La tarea es determinar el número de puntos (con coordenadas enteras) tal que la suma de las distancias de Manhattan desde estos puntos hasta los N puntos se minimice . 

La distancia de Manhattan es la suma de las distancias entre dos puntos medidos a lo largo de ejes en ángulo recto. En un plano con p1 en (x1, y1) y p2 en (x2, y2) , es |x1 – x2| + |y1 – y2| .

Ejemplos:  

Entrada: N = 3, K = 3, 
Puntos = { {1, 1, 1}, 
                {2, 2, 2}, 
                {3, 3, 3} }  
Salida: 1
Explicación : De {2,2,2} , la suma de las distancias de Manhattan a otros 2 puntos es mínima

Entrada: N = 4, K = 4, 
Puntos = { {1, 6, 9, 6}, 
                {5, 2, 5, 7}, 
                {2, 0, 1, 5}, 
                {4, 6, 3, 9} }  
Salida: 90

Enfoque: El enfoque se basa en la clasificación . k

• Caso -1 Cuando N es impar : Se puede resolver sobre la base de la siguiente observación
  • El número de tales puntos óptimos siempre será 1 porque después de clasificarlos en todas las K dimensiones, habrá solo un punto medio donde la suma de las distancias de Manhattan alcanzará el valor mínimo.

Por ejemplo: Considere la expresión |x-3| + |x-5| + |x-8|. Esta alcanza su valor mínimo sólo en un único punto x = 5.

• Caso-2 Cuando N es par : La siguiente observación ayuda a resolver el problema.
  • Ordenar los puntos sobre la base de una dimensión.
  • Para cada dimensión, habrá 2 índices medianos, a saber, (N/2)-1 y (N/2) .
    • Todos los números en el rango [ Puntos [(N/2) -1], Puntos [N/2] ] actuarán como medianas donde la suma de las distancias de Manhattan alcanzará el valor mínimo.
    • Entonces, el número total de coordenadas medianas para esa dimensión será Points[(N/2)] – Points[(N/2)-1]+1 .
  • De manera similar, encuentre el número de coordenadas medianas en todas las dimensiones después de clasificar los números en función de esa dimensión, y su producto formará el número total de tales puntos óptimos en el espacio de K -dimensional.

Por ejemplo: Considere la expresión |x-3| + |x-5| + |x-8| + |x-10|. Este alcanza su valor mínimo para todo x en el rango [5,8]. Entonces habrá (8-5)+1 = 4 número de tales x. De manera similar, encuentre para todas las K dimensiones.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the required number
// of points which minimizes the sum
// of Manhattan distances
int NumberOfPointsWithMinDistance(
    int n, int k, vector<vector<int> >& point)
{
    // Sorting points in all k dimension
    for (int i = 0; i < k; ++i)
        sort(point[i].begin(), point[i].end());
 
    // When n is odd
    if (n % 2 == 1) {
        return 1;
    }
 
    // When n is even
    int ans = 1;
    for (int i = 0; i < k; ++i) {
 
        int possible_points
            = point[i][n / 2] -
            point[i][(n / 2) - 1] + 1;
        ans = ans * possible_points;
    }
    return ans;
}
 
int main()
{
    int N = 4, K = 4;
    vector<vector<int> >
        Points = { { 1, 5, 2, 4 },
                   { 6, 2, 0, 6 },
                   { 9, 5, 1, 3 },
                   { 6, 7, 5, 9 } };
 
    cout << NumberOfPointsWithMinDistance(N, K, Points);
    return 0;
}

// Java implementation of above approach
import java.util.*;
class GFG
{
 
  // Function to find the required number
  // of points which minimizes the sum
  // of Manhattan distances
  static int NumberOfPointsWithMinDistance(
    int n, int k, int[][] point)
  {
 
    // Sorting points in all k dimension
    for (int i = 0; i < k; ++i)
      Arrays.sort(point[i]);
 
    // When n is odd
    if (n % 2 == 1) {
      return 1;
    }
 
    // When n is even
    int ans = 1;
    for (int i = 0; i < k; ++i) {
 
      int possible_points
        = point[i][n / 2] -
        point[i][(n / 2) - 1] + 1;
      ans = ans * possible_points;
    }
    return ans;
  }
 
  public static void main(String[] args)
  {
    int N = 4, K = 4;
    int[][]
      Points = { { 1, 5, 2, 4 },
                { 6, 2, 0, 6 },
                { 9, 5, 1, 3 },
                { 6, 7, 5, 9 } };
 
    System.out.print(NumberOfPointsWithMinDistance(N, K, Points));
  }
}
 
// This code is contributed by gauravrajput1

# Python code for the above approach
 
# Function to find the required number
# of points which minimizes the sum
# of Manhattan distances
def NumberOfPointsWithMinDistance(n, k, points):
   
    # Sorting points in all k dimension
    for i in range(k):
        points[i].sort()
 
    # When n is odd
    if (n % 2 == 1):
        return 1
 
    # When n is even
    ans = 1
    for i in range(k):
 
        possible_points = points[i][(n // 2)] - points[i][(n // 2) - 1] + 1
        ans = ans * possible_points
    return ans
 
#  Drive code
N = 4
K = 4
Points = [[1, 5, 2, 4], [6, 2, 0, 6], [9, 5, 1, 3], [6, 7, 5, 9]]
print(NumberOfPointsWithMinDistance(N, K, Points))
 
# This code is contributed by gfgking

// C# implementation of above approach
using System;
using System.Linq;
public class GFG
{
 
  // Function to find the required number
  // of points which minimizes the sum
  // of Manhattan distances
  static int NumberOfPointsWithMinDistance(
    int n, int k, int[,] point)
  {
    int []x = null;
 
    // Sorting points in all k dimension
    for (int i = 0; i < k; ++i)
    {
      x = GetRow(point, i);
      Array.Sort(x);
      for(int j = 0; j < x.GetLength(0); j++)
        point[i,j] = x[j]; 
    }
 
    // When n is odd
    if (n % 2 == 1) {
      return 1;
    }
 
    // When n is even
    int ans = 1;
    for (int i = 0; i < k; ++i) {
 
      int possible_points
        = point[i,n / 2] -
        point[i,(n / 2) - 1] + 1;
      ans = ans * possible_points;
    }
    return ans;
  }
  public static int[] GetRow(int[,] matrix, int row)
  {
    var rowLength = matrix.GetLength(1);
    var rowVector = new int[rowLength];
 
    for (var i = 0; i < rowLength; i++)
      rowVector[i] = matrix[row, i];
 
    return rowVector;
  }
  public static void Main(String[] args)
  {
    int N = 4, K = 4;
    int[,]
      Points = { { 1, 5, 2, 4 },
                { 6, 2, 0, 6 },
                { 9, 5, 1, 3 },
                { 6, 7, 5, 9 } };
 
    Console.Write(NumberOfPointsWithMinDistance(N, K, Points));
  }
}
 
// This code is contributed by 29AjayKumar

<script>
       // JavaScript code for the above approach
 
       // Function to find the required number
       // of points which minimizes the sum
       // of Manhattan distances
       function NumberOfPointsWithMinDistance(
           n, k, points) {
           // Sorting points in all k dimension
           for (let i = 0; i < k; ++i)
               points[i].sort(function (a, b) { return a - b })
 
           // When n is odd
           if (n % 2 == 1) {
               return 1;
           }
 
           // When n is even
           let ans = 1;
           for (let i = 0; i < k; ++i) {
 
               let possible_points
                   = points[i][Math.floor(n / 2)] -
                   points[i][Math.floor(n / 2) - 1] + 1;
               ans = ans * possible_points;
           }
           return ans;
       }
 
 
       let N = 4, K = 4;
       let
           Points = [[1, 5, 2, 4],
           [6, 2, 0, 6],
           [9, 5, 1, 3],
           [6, 7, 5, 9]];
 
       document.write(NumberOfPointsWithMinDistance(N, K, Points));
 
 // This code is contributed by Potta Lokesh
   </script>

90

Complejidad de tiempo : O(K * N * log(N))
Espacio auxiliar : O(1)