Олимпиадный тренинг

Задача . Взвешенные соседи на плоскости


Задача

Темы:

Каждый известный объект описывается двумя признаками — координатами (xi, yi) — и значением vi. Нужно предсказать значение для новых точек методом k ближайших соседей, в котором ближние соседи важнее дальних:

  1. расстояние — обычное евклидово: √((xi − x)² + (yi − y)²);
  2. объекты упорядочиваются по возрастанию расстояния; при равных расстояниях раньше идёт объект, который стоит раньше во входных данных; первые k — соседи;
  3. если среди соседей есть объекты на расстоянии 0, прогноз — среднее значение v только этих объектов;
  4. иначе у каждого соседа вес w = 1 / расстояние, а прогноз — взвешенное среднее: Σ w·v / Σ w.

Входные данные

В первой строке — n и k (1 ≤ k ≤ n ≤ 1000). В каждой из следующих n строк — три целых числа xi, yi, vi (|xi|, |yi| ≤ 104, 0 ≤ vi ≤ 105). Затем число m (1 ≤ m ≤ 500) и m строк по два целых числа — координаты новой точки (по модулю не больше 104).

Выходные данные

Для каждой новой точки в отдельной строке — прогноз, округлённый до ближайшего целого. Гарантируется, что дробная часть точного прогноза отличается от 0,5 больше чем на 10−6.

Пример

Ввод Вывод
3 2
0 0 10
4 0 40
0 10 100
2
4 0
0 5
40
55

Пояснение

Точка (4, 0) совпадает со вторым объектом: расстояние 0, прогноз — его значение 40. Для точки (0, 5) оба ближайших объекта, (0, 0) и (0, 10), находятся на расстоянии 5, их веса равны, прогноз (10 + 100) / 2 = 55.

Подсказка: чтобы выбрать соседей, сравнивайте квадраты расстояний — это целые числа, и при сравнении не возникает ошибок округления. Корень нужен только для весов.


Примеры
№Входные данныеВыходные данные
1
3 2
0 0 10
4 0 40
0 10 100
2
4 0
0 5
40
55
Статистика успешных решений по компиляторам
 Кол-во
Python2