Closest Point
Национална Олимпиада по Информатика 2015, Контрола 1
Time Limit: 1.5s, Memory Limit: 64MiB
Някога пробвали ли сте да правите няколко тотално различни неща едновремено? Ако да, сигурно знаете, че обикновено това води до създаване на огромни каши.

Такъв е и случаят с Ели. Тя се занимаваше с три доста сложни сами по себе си проекта: да изследва дали има паралелни вселени, да направи телепортатор и да изобрети машина за времето. Крайният резултат беше телепортатор, който освен в пространството може да я премести и във времето и/или в паралелна вселена.

"Готино", навярно си мислите вие, но всъщност нейното изобретение има своите недостатъци. Например, телепортирайки се с нейния междузвезден кораб, момичето може да попадне в произволни координати (X, Y, Z) във време T във вселена U. Както може би се досещате, след като попаднете на произволно място, в произволно време в произволна вселена, нещата не са толкова розови.

Експло(р)ататорският дух на Ели, обаче, все още не я е напуснал! След всяка телепортация, тя иска да намери най-близкото слънце до нея и да провери за разумни същества там. Момичето има звездна карта за всяка паралелна вселена, и всяко време, задаваща координатите на всяко от слънцата там. Все пак, обаче й е трудно да намери най-близкото слънце до позицията, в която се е озовала. Сега Ели се е обърнала към вас да напишете програма, която прави това.

Задачата ви всъщност е по-генерална: по дадени N точки в K-мерно пространство да може да отговори на Q заявки от типа: "Колко е разстоянието до най-близката от тези N точки от текущите ми координати (C1, C2, ..., CK)?" Считаме, че разстоянието между две точки (Ci1, Ci2, ..., CiK) и (Cj1, Cj2, ..., CjK) в K-мерно пространство е стандартното Евклидоворазстояние: sqrt((Ci1 – Cj1)2 + (Ci2 – Cj2)2 + ... + (CiK - CjK)2)), където sqrt() е функцията корен квадратен.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K, задаващи броя точки и размерността на пространството, в което се намират. Следват N реда с по K числа Di1 Di2 ... DiK - координатите на точките в това пространство. Следва ред с едно цяло число Q - броя заявки, на които се иска да отговорите. Самите заявки са зададени на следващите Q реда, отново като K-торки Ci1 Ci2 ... CiK. Точките ще са избрани по произволен начин в K-мерен куб. Възможно е да има съвпадащи точки както сред входните N, така и сред тези от въпросите, но (с изключение на примера) това е по случайност (в следствие на произволния избор на координатите).
Изход
За всяка от Q-те заявки изпечатайте на единствен ред по едно дробно число - минималното разстояние до някоя от N-те точки. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ K ≤ 5
  • 1 ≤ Q ≤ 100,000
  • -1,000,000 ≤ Dij, Cij ≤ 1,000,000
Примерен Вход Примерен Изход
11 4 -3 -9 9 -5 8 -4 5 -10 7 -5 -4 -6 0 -9 -5 10 10 10 -2 10 -7 8 3 -2 3 -5 5 -9 -9 9 -5 -4 3 5 0 -6 5 6 9 -6 3 -5 5 -9 5 -9 9 -9 -1 7 2 -8 7 6 5 -9 -8 7 2 -8 7 0 -9 -5 10 5.000000000 10.862780491 9.695359715 10.862780491 0.000000000
Ели се намира в четиримерното пространство и разглежда 11 слънца (точки). Тя задава 5 въпроса:
  1. За точката (-9, 9, -9, -1). Най-близката до нея точка от зададените единайсет е (-9, 9, -5, -4) на разстояние 5.
  2. За точката (7, 2, -8, 7). Най-близката до нея точка от входните е (10, 10, -2, 10) на разстояние 10.862780491.
  3. За точката (6, 5, -9, -8). Най-близката до нея точка от входните е (3, 5, 0, -6) на разстояние 9.695359715.
  4. Въпросът е същият като въпрос 2.
  5. За точката (0, -9, -5, 10). Точка с тези координати присъства в дадените N, затова отговорът е 0.000.
Мрън!