Оптимальний Космічний Шлях
Це 2180 рік нашої ери, людство тільки почало залишати Землю і поширювати цивілізацію в космосі. ACM (Асоціація Космічного Машинізму) відповідає за весь процес переселення, і цей процес в основному фінансується IBM (Міжпланетні Балістичні Машини). Тисячі космічних міст побудовані у відкритому космосі, і щоб підтримувати універсальний робочий час (схід і захід сонця одночасно у всіх космічних містах), вони побудовані на одній уявній площині. Отже, розташування міст можна виразити у вигляді двовимірних декартових координат.
Міста розташовані далеко одне від одного, і єдиний спосіб дістатися з одного міста в інше - це використання шатлів-ракет. Але з попереднього досвіду ACM знає, що подорож дорогами набагато дешевша, ніж подорож ракетами. Тому вони вирішили побудувати кілька доріг. Але будівництво доріг між кожною парою міст дуже дороге. Тому вони планують побудувати супер космічний шлях (SSW), який буде прямою дорогою. Коли комусь потрібно подорожувати з міста c_1 до міста c_2, він спочатку подорожує з c_1 до найближчої точки SSW на ракеті, і рухається вздовж SSW до точки, яка найближча до c_2. Потім звідти він йде до c_2, використовуючи іншу ракету. Вартість руху вздовж дороги пропорційна відстані, але вартість польоту на ракетах пропорційна квадрату відстані. Тому ви повинні побудувати SSW у такому положенні, щоб загальна вартість подорожі ракетами за календарний рік була мінімальною. Ви можете припустити, що:
Міста настільки малі в порівнянні з відстанню між ними, що їх можна вважати точками на двовимірній декартовій системі координат.
SSW настільки вузький у порівнянні з відстанню між містами, що його можна вважати прямою лінією. Довжина SSW може збільшуватися нескінченно в обох напрямках, якщо загальна вартість подорожі ракетами зменшується при цьому.
Для простоти можна припустити, що загальна кількість вхідних і вихідних ракет з кожного міста однакова.
Іноді одне місто може бути позначене як супер місто, яке є центром усіх активностей. У такому випадку загальна кількість вхідних і вихідних рейсів цього міста в M разів вища, ніж у звичайного міста.
Припустимо, що всі ракети літають по прямій лінії.
Враховуючи розташування всіх міст, ви повинні знайти місце для SSW, для якого загальна вартість подорожі ракетами є мінімальною. І ви повинні визначити мінімальну середню вартість за політ ракети, припускаючи, що вартість польоту на v одиниць відстані дорівнює v^2.
Вхідні дані
Вхідний файл містить менше ніж 50 тестових випадків. Опис кожного тестового випадку наведено нижче:
Кожен тестовий випадок починається з двох цілих чисел N (0 < N ≤ 10000) і Q (0 < Q ≤ 100). Тут N - загальна кількість міст, побудованих у відкритому космосі, а Q - загальна кількість запитів. Кожен з наступних N рядків містить два числа з плаваючою комою, x_i, y_i (0.0 ≤ x_i, y_i ≤ 1000.0), які позначають координати i-го міста. Міста нумеруються від 0 до N-1 у порядку їх появи у вхідному файлі. Кожен з наступних Q рядків містить два цілі числа S (0 ≤ S ≤ N-1) і M (1 < M ≤10000). Тут S позначає ідентифікатор супер міста, а M позначає, що загальна кількість вхідних і вихідних рейсів у супер місті в M разів вища, ніж у звичайного міста.
Рядок, що містить два нулі, завершує вхід. Цей рядок не слід обробляти.
Вихідні дані
Для кожного тестового випадку виведіть Q+2 рядки виходу. Перший рядок містить номер випадку, за яким слідує двокрапка. Другий рядок містить число з плаваючою комою, яке позначає мінімальну середню вартість за політ ракети для оптимального супер космічного шляху (припускаючи, що всі міста звичайні). Цей рядок супроводжується Q рядками, по одному для кожного запиту. Цей рядок містить серійний номер запиту, за яким слідує число з плаваючою комою. Це число позначає мінімальну середню вартість для оптимального супер космічного шляху, припускаючи, що S-те місто є супер містом, а всі інші міста звичайні. Усі числа з плаваючою комою у виході повинні мати п'ять цифр після десяткової точки. Подивіться на вихід для зразкового вводу для деталей. Ви можете припустити, що для всіх чисел з плаваючою комою абсолютна похибка менша ніж 10^{-5} буде ігнорована.