Dada una array mat[][] que consta de N pares de la forma {x, y}, cada uno de los cuales denota coordenadas de N puntos, la tarea es encontrar la suma mínima de las distancias euclidianas a todos los puntos.
Ejemplos:
Entrada: mat[][] = { { 0, 1}, { 1, 0 }, { 1, 2 }, { 2, 1 }}
Salida : 4
Explicación:
Promedio del conjunto de puntos, es decir Centroide = (( 0+1+1+2)/4, (1+0+2+1)/4) = (1, 1).
La distancia euclidiana de cada punto desde el centroide es {1, 1, 1, 1}
Suma de todas las distancias = 1 + 1 + 1 + 1 = 4
Entrada: mat[][] = { { 1, 1}, { 3, 3 }}
Salida: 2.82843
Enfoque:
dado que la tarea es minimizar la distancia euclidiana a todos los puntos, la idea es calcular la mediana de todos los puntos . Mediana Geométrica generaliza el concepto de mediana a dimensiones superiores
Siga los pasos a continuación para resolver el problema:
- Calcula el centroide de todas las coordenadas dadas, obteniendo el promedio de los puntos.
- Encuentre la distancia euclidiana de todos los puntos desde el centroide.
- Calcule la suma de estas distancias e imprímala como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate Euclidean distance
double find(double x, double y,
vector<vector<int> >& p)
{
double mind = 0;
for (int i = 0; i < p.size(); i++) {
double a = p[i][0], b = p[i][1];
mind += sqrt((x - a) * (x - a)
+ (y - b) * (y - b));
}
return mind;
}
// Function to calculate the minimum sum
// of the euclidean distances to all points
double getMinDistSum(vector<vector<int> >& p)
{
// Calculate the centroid
double x = 0, y = 0;
for (int i = 0; i < p.size(); i++) {
x += p[i][0];
y += p[i][1];
}
x = x / p.size();
y = y / p.size();
// Calculate distance of all
// points
double mind = find(x, y, p);
return mind;
}
// Driver Code
int main()
{
// Initializing the points
vector<vector<int> > vec
= { { 0, 1 }, { 1, 0 }, { 1, 2 }, { 2, 1 } };
double d = getMinDistSum(vec);
cout << d << endl;
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function to calculate Euclidean distance
static double find(double x, double y,
int [][] p)
{
double mind = 0;
for(int i = 0; i < p.length; i++)
{
double a = p[i][0], b = p[i][1];
mind += Math.sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
// Function to calculate the minimum sum
// of the euclidean distances to all points
static double getMinDistSum(int [][]p)
{
// Calculate the centroid
double x = 0, y = 0;
for(int i = 0; i < p.length; i++)
{
x += p[i][0];
y += p[i][1];
}
x = x / p.length;
y = y / p.length;
// Calculate distance of all
// points
double mind = find(x, y, p);
return mind;
}
// Driver Code
public static void main(String[] args)
{
// Initializing the points
int [][]vec = { { 0, 1 }, { 1, 0 },
{ 1, 2 }, { 2, 1 } };
double d = getMinDistSum(vec);
System.out.print(d + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach from math import sqrt # Function to calculate Euclidean distance def find(x, y, p): mind = 0 for i in range(len(p)): a = p[i][0] b = p[i][1] mind += sqrt((x - a) * (x - a) + (y - b) * (y - b)) return mind # Function to calculate the minimum sum # of the euclidean distances to all points def getMinDistSum(p): # Calculate the centroid x = 0 y = 0 for i in range(len(p)): x += p[i][0] y += p[i][1] x = x // len(p) y = y // len(p) # Calculate distance of all # points mind = find(x, y, p) return mind # Driver Code if __name__ == '__main__': # Initializing the points vec = [ [ 0, 1 ], [ 1, 0 ], [ 1, 2 ], [ 2, 1 ] ] d = getMinDistSum(vec) print(int(d)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to calculate Euclidean distance
static double find(double x, double y,
int [,] p)
{
double mind = 0;
for(int i = 0; i < p.GetLength(0); i++)
{
double a = p[i,0], b = p[i,1];
mind += Math.Sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
// Function to calculate the minimum sum
// of the euclidean distances to all points
static double getMinDistSum(int [,]p)
{
// Calculate the centroid
double x = 0, y = 0;
for(int i = 0; i < p.GetLength(0); i++)
{
x += p[i,0];
y += p[i,1];
}
x = x / p.Length;
y = y / p.Length;
// Calculate distance of all
// points
double mind = find(x, y, p);
return mind;
}
// Driver Code
public static void Main(String[] args)
{
// Initializing the points
int [,]vec = { { 0, 1 }, { 1, 0 },
{ 1, 2 }, { 2, 1 } };
int d = (int)getMinDistSum(vec);
Console.Write(d + "\n");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate Euclidean distance
function find(x, y, p)
{
let mind = 0;
for(let i = 0; i < p.length; i++)
{
let a = p[i][0], b = p[i][1];
mind += Math.sqrt((x - a) * (x - a) +
(y - b) * (y - b));
}
return mind;
}
// Function to calculate the minimum sum
// of the euclidean distances to all points
function getMinDistSum(p)
{
// Calculate the centroid
let x = 0, y = 0;
for(let i = 0; i < p.length; i++)
{
x += p[i][0];
y += p[i][1];
}
x = x / p.length;
y = y / p.length;
// Calculate distance of all
// points
let mind = find(x, y, p);
return mind;
}
// Driver Code
// Initializing the points
let vec = [[ 0, 1 ], [ 1, 0 ],
[ 1, 2 ], [ 2, 1 ]];
let d = getMinDistSum(vec);
document.write(d);
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA