# Find sum of Kth largest Euclidian distance after removing ith coordinate one at a time

Given **N** integer coordinates where **X[i]** denotes the x-coordinate and **Y[i]** denotes the y-coordinate of the **i ^{th}** coordinate, the task is to find the sum of

**K**largest euclidian distance between all the coordinate pairs except the

^{th}**i**coordinate for all possible values of

^{th}**i**in the range

**[1, N]**.

**Examples:**

Input:X[] = {0, 0, 1, 1}, Y[] = {0, 1, 0, 1}, K = 2Output:4Explanation:

- The coordinates except the 1st coordinate are {{0, 1}, {1, 0}, {1, 1}}. Their respective euclidian distances are {1.414, 1, 1}. Since K = 2, the second largest euclidian distance = 1.
- The coordinates except the 2nd coordinate are {{0, 0}, {1, 0}, {1, 1}}. Their respective euclidian distances are {1, 1, 1.414}. The second largest euclidian distance = 1.
- The coordinates except the 3rd coordinate are {{0, 1}, {0, 0}, {1, 1}}. Their respective euclidian distances are {1, 1.414, 1}. The second largest euclidian distance = 1.
- The coordinates except the 4th coordinate are {{0, 1}, {1, 0}, {0, 0}}. Their respective euclidian distances are {1.414, 1, 1}. The second largest euclidian distance = 1.
The sum of all second largest euclidian distances is 4.

Input:X[] = {0, 1, 1}, Y[] = {0, 0, 1}, K = 1Output:3.41421

**Approach:** The given problem can be solved by following the below steps:

- Create a vector
**distances[]**which store index**p**,**q**, and the euclidian distance between the**p**and^{th}**q**coordinate for all valid unordered pairs of^{th}**(p, q)**in the range**[1, N]**. - Sort the vector
**distances**in the order of decreasing distances. - For all values of
**i**in the range**[1, N]**, perform the following operation:- Create a variable
**cnt**, which keeps track of the index of**K**largest element in^{th}**distances**vector. Initially,**cnt = 0**. - Iterate through the vector
**distances**using a variable**j**, and increment the value of**cnt**by**1**if**i != p**and**i != q**where**(p, q)**are the indices of coordinates stored in**distances[j]**. - If
**cnt = K**, add the distance at current index**j**in**distances**vector into a variable**ans**. - The value stored in
**ans**is the required answer.

- Create a variable

Below is the implementation of the above approach:

## 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 euclidian 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 euclidian` ` ` `// 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;` `}` |

## 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 euclidian distances` ` ` `# between all pairs of coordinates` ` ` `for` `i ` `in` `range` `(N):` ` ` `for` `j ` `in` `range` `(i ` `+` `1` `, N, ` `1` `):` ` ` `# Stores the square of euclidian` ` ` `# 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.` |

**Output:**

3.41421

**Time Complexity:** O(N^{2}*log N + K*N^{2})**Auxiliary Space:** O(N^{2})

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**