Dadas N coordenadas enteras donde X[i] denota la coordenada x e Y[i] denota la coordenada y de la i -ésima coordenada, la tarea es encontrar la suma de la K -ésima distancia euclidiana más grande entre todos los pares de coordenadas excepto el i -ésima coordenada para todos los valores posibles de i en el rango [1, N] .
Ejemplos:
Entrada: X[] = {0, 0, 1, 1}, Y[] = {0, 1, 0, 1}, K = 2
Salida: 4
Explicación:
- Las coordenadas excepto la primera coordenada son {{0, 1}, {1, 0}, {1, 1}}. Sus distancias euclidianas respectivas son {1.414, 1, 1}. Dado que K = 2, la segunda distancia euclidiana más grande = 1.
- Las coordenadas excepto la segunda coordenada son {{0, 0}, {1, 0}, {1, 1}}. Sus respectivas distancias euclidianas son {1, 1, 1.414}. La segunda distancia euclidiana más grande = 1.
- Las coordenadas excepto la tercera coordenada son {{0, 1}, {0, 0}, {1, 1}}. Sus respectivas distancias euclidianas son {1, 1.414, 1}. La segunda distancia euclidiana más grande = 1.
- Las coordenadas excepto la cuarta coordenada son {{0, 1}, {1, 0}, {0, 0}}. Sus distancias euclidianas respectivas son {1.414, 1, 1}. La segunda distancia euclidiana más grande = 1.
La suma de todas las segundas distancias euclidianas más grandes es 4.
Entrada: X[] = {0, 1, 1}, Y[] = {0, 0, 1}, K = 1
Salida: 3,41421
Enfoque: El problema dado se puede resolver siguiendo los siguientes pasos:
- Cree un vector distances[] que almacene el índice p , q y la distancia euclidiana entre las coordenadas p th y q th para todos los pares no ordenados válidos de (p, q) en el rango [1, N] .
- Ordena las distancias vectoriales en orden de distancias decrecientes.
- Para todos los valores de i en el rango [1, N] , realice la siguiente operación:
- Cree una variable cnt , que realiza un seguimiento del índice del elemento más grande K en el vector de distancias . Inicialmente, cnt = 0 .
- Iterar a través de las distancias vectoriales usando una variable j e incrementar el valor de cnt en 1 si i != p y i != q donde (p, q) son los índices de las coordenadas almacenadas en distances[j] .
- Si cnt = K , agregue la distancia en el índice actual j en el vector de distancias en una variable ans .
- El valor almacenado en ans es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of the Kth
// maximum distance after excluding the
// ith coordinate for all i over the
// range [1, N]
double sumMaxDistances(int X[], int Y[],
int N, int K)
{
// Stores (p, q) and the square of
// distance between pth and qth
// coordinate
vector<pair<int, pair<int, int> > > distances;
// Find the euclidean distances
// between all pairs of coordinates
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// Stores the square of euclidean
// distance between the ith and
// the jth coordinate
int d = (X[i] - X[j]) * (X[i] - X[j])
+ (Y[i] - Y[j]) * (Y[i] - Y[j]);
// Insert into distances
distances.push_back({ d, { i, j } });
}
}
// Stores the final answer
double ans = 0;
// Sort the distances vector in the
// decreasing order of distance
sort(distances.begin(), distances.end(),
greater<pair<int, pair<int, int> > >());
// Iterate over all i in range [1, N]
for (int i = 0; i < N; i++) {
// Stores the square of Kth maximum
// distance
int mx = -1;
// Stores the index of Kth maximum
// distance
int cnt = 0;
// Loop to iterate over distances
for (int j = 0; j < distances.size(); j++) {
// Check if any of (p, q) in
// distances[j] is equal to i
if (distances[j].second.first != i
&& distances[j].second.second != i) {
cnt++;
}
// If the current index is the
// Kth largest distance
if (cnt == K) {
mx = distances[j].first;
break;
}
}
// If Kth largest distance exists
// then add it into ans
if (mx != -1) {
// Add square root of mx as mx
// stores the square of distance
ans += sqrt(mx);
}
}
// Return the result
return ans;
}
// Driver Code
int main()
{
int X[] = { 0, 1, 1 };
int Y[] = { 0, 0, 1 };
int K = 1;
int N = sizeof(X) / sizeof(X[0]);
cout << sumMaxDistances(X, Y, N, K);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
import java.util.*;
import java.util.Collections;
// User defined Pair class
class Pair {
int first;
int second;
// Constructor
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// User defined Pair with one element int and other as a
// pair
class Pair_next {
int first;
Pair second;
// constructor
public Pair_next(int first, Pair second)
{
this.first = first;
this.second = second;
}
}
// class to sort the elements in
// decreasing order of first element
class cmp implements Comparator<Pair_next> {
public int compare(Pair_next p1, Pair_next p2)
{
return p2.first - p1.first;
}
}
public class GFG {
// Function to find the sum of the Kth
// maximum distance after excluding the
// ith coordinate for all i over the
// range [1, N]
static double sumMaxDistances(int X[], int Y[], int N,
int K)
{
// Stores (p, q) and the square of
// distance between pth and qth
// coordinate
Vector<Pair_next> distances
= new Vector<Pair_next>();
// Find the euclidean distances
// between all pairs of coordinates
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
// Stores the square of euclidean
// distance between the ith and
// the jth coordinate
int d = (X[i] - X[j]) * (X[i] - X[j])
+ (Y[i] - Y[j]) * (Y[i] - Y[j]);
// Insert into distances
Pair temp_pair = new Pair(i, j);
Pair_next temp
= new Pair_next(d, temp_pair);
distances.add(temp);
}
}
// Stores the final answer
double ans = 0;
// Sort the distances vector in the
// decreasing order of distance
Collections.sort(distances, new cmp());
// Iterate over all i in range [1, N]
for (int i = 0; i < N; i++) {
// Stores the square of Kth maximum
// distance
int mx = -1;
// Stores the index of Kth maximum
// distance
int cnt = 0;
// Loop to iterate over distances
for (int j = 0; j < distances.size(); j++) {
// Check if any of (p, q) in
// distances[j] is equal to i
if (distances.get(j).second.first != i
&& distances.get(j).second.second
!= i) {
cnt++;
}
// If the current index is the
// Kth largest distance
if (cnt == K) {
mx = distances.get(j).first;
break;
}
}
// If Kth largest distance exists
// then add it into ans
if (mx != -1) {
// Add square root of mx as mx
// stores the square of distance
ans += Math.sqrt(mx);
}
}
// Return the result
return ans;
}
// Driver Code
public static void main(String[] args)
{
int X[] = { 0, 1, 1 };
int Y[] = { 0, 0, 1 };
int K = 1;
int N = X.length;
System.out.println(sumMaxDistances(X, Y, N, K));
}
}
// This code is contributed by rj13to.
Python3
# Python 3 program for the above approach from math import sqrt # Function to find the sum of the Kth # maximum distance after excluding the # ith coordinate for all i over the # range [1, N] def sumMaxDistances(X, Y, N, K): # Stores (p, q) and the square of # distance between pth and qth # coordinate distances = [] # Find the euclidean distances # between all pairs of coordinates for i in range(N): for j in range(i + 1, N, 1): # Stores the square of euclidean # distance between the ith and # the jth coordinate d = int(X[i] - X[j]) * int(X[i] - X[j]) + int(Y[i] - Y[j]) * int(Y[i] - Y[j]) # Insert into distances distances.append([d,[i, j]]) # Stores the final answer ans = 0 # Sort the distances vector in the # decreasing order of distance distances.sort(reverse = True) # Iterate over all i in range [1, N] for i in range(N): # Stores the square of Kth maximum # distance mx = -1 # Stores the index of Kth maximum # distance cnt = 0 # Loop to iterate over distances for j in range(0,len(distances), 1): # Check if any of (p, q) in # distances[j] is equal to i if (distances[j][1][0] != i and distances[j][1][0] != i): cnt += 1 # If the current index is the # Kth largest distance if (cnt == K): mx = distances[j][0] break # If Kth largest distance exists # then add it into ans if (mx != -1): # Add square root of mx as mx # stores the square of distance ans += (sqrt(mx)) # Return the result return ans # Driver Code if __name__ == '__main__': X = [0, 1, 1] Y = [0, 0, 1] K = 1 N = len(X) print(sumMaxDistances(X, Y, N, K)) # This code is contributed by ipg2016107.
Producción:
3.41421
Complejidad de Tiempo: O(N 2 *log N + K*N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA