Оптимальный космический путь
Это 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} будет игнорироваться.