Найдите сумму K-го наибольшего евклидова расстояния после удаления i-й координаты по одной за раз

Для заданных N целочисленных координат, где X[i] обозначает координату x, а Y[i] обозначает координату y i ^-й координаты, задача состоит в том, чтобы найти сумму K ^-го наибольшего евклидова расстояния между всеми парами координат, кроме i ^-я координата для всех возможных значений i в диапазоне [1, N] .

Примеры:

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

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

The sum of all second largest euclidean distances is 4.

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

Подход: Данную проблему можно решить, выполнив следующие шаги:

• Создайте вектор Distances[] , в котором хранятся индексы p , q и евклидово расстояние между p ^-й и q ^-й координатами для всех допустимых неупорядоченных пар (p, q) в диапазоне [1, N] .
• Отсортируйте векторные расстояния в порядке убывания расстояний.
• Для всех значений i в диапазоне [1, N] выполните следующую операцию:
  • Создайте переменную cnt , которая отслеживает индекс K ^-го самого большого элемента в векторе расстояний . Первоначально cnt = 0 .
  • Выполните итерацию по векторным расстояниям , используя переменную j , и увеличьте значение cnt на 1 , если i != p и i != q , где (p, q) — индексы координат, сохраненные в Distances[j] .
  • Если cnt = K , добавьте расстояние с текущим индексом j в векторе расстояний в переменную ans .
  • Значение, хранящееся в ans , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² *log N + K*N ² )
Вспомогательное пространство: O(N ² )