Задача №114666. Растягивание плоскости
Игорь очень любит геометрию, а поэтому он купил себе плоскость, на которой отмечены \(n\) точек, \(i\)-я из них имеет координаты \((x_i, y_i)\).
Посмотрев на эти точки, Игорь быстро нашёл пару самых удалённых. Однако этого ему было мало, а поэтому для \(q\) чисел \(\alpha_1\), \(\alpha_2\), \(\alpha_3\), ..., \(\alpha_q\) Игорь хочет узнать, каким станет максимальное расстояние между парой точек, если растянуть плоскость в \(\alpha_j\) раз по \(x\)-координате.
Более формально, у Игоря есть \(q\) запросов, в \(j\)-м из которых для числа \(\alpha_j\) Игорь хочет найти расстояние между двумя наиболее удалёнными точками в множестве, состоящем из \(n\) точек с координатами \((x_i \cdot \alpha_j, y_i)\). Помогите Игорю ответить на эти запросы.
Каждый тест состоит из нескольких наборов входных данных. В первой строке вводятся два целых числа \(t\) и \(g\) (\(1 \le t \le 250\,000\), \(0 \le g \le 9\)) — число наборов входных данных и номер группы тестов, под дополнительные ограничения которой подходит данный тест. Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных вводятся два целых числа \(n\) и \(q\) \((2 \le n \le 500\,000, 1 \le q \le 500\,000)\) — количество точек и количество запросов.
В следующих \(n\) строках вводятся описание точек, в каждой строке вводятся по два целых числа \(x_i\) и \(y_i\) \((-10^9 \le x_i, y_i \le 10^9)\) — координаты \(i\)-й точки. Гарантируется, что координаты всех точек в каждом наборе входных данных различны.
В следующих \(q\) строках вводятся описания запросов, в каждой строке вводится по одному вещественному числу \(\alpha_j\) \((1 \le \alpha_j \le 10^9)\) — коэффициенты, на которые будут умножаться \(x\)-координаты точек в \(j\)-м запросе.
Обозначим за \(N\) сумму \(n_i\) по всем наборам входных данных, а за \(Q\) — сумму \(q_i\) по всем наборам входных данных. Гарантируется, что \(N, Q \le 500\,000\).
Для каждого набора входных данных выведите \(q\) строк, в \(i\)-й строке должно содержаться единственное вещественное число — ответ на \(i\)-й запрос. Ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает \(10^{-6}\). Более формально, если \(a\) — ваш ответ, а \(b\) — ответ жюри, то должно выполняться \(\frac{|a-b|}{\max(b,1)} \le 10^{-6}\).
При растяжении с коэффициентом 1 наиболее удалёнными точками будут точки с номерами 1 и 5, их координаты будут равны \((0, 0)\) и \((0, 4)\).
При растяжении с коэффициентом 2.5 наиболее удалёнными точками будут точки с номерами 2 и 4, их координаты будут равны \((2.5, 1)\) и \((-2.5, 3)\).
Во втором наборе входных данных максимальное расстояние будет достигаться следующими парами точек:
-
в первом запросе максимальное расстояние будет достигаться между точками с номерами 3 и 7, их координаты будут равны \((14,13)\) и \((-14,13)\),
-
во втором запросе максимальное расстояние будет достигаться между точками с номерами 1 и 5, их координаты будут равны \((0,0)\) и \((0, 15)\),
-
в третьем запросе максимальное расстояние будет достигаться между точками с номерами 3 и 7, их координаты будут равны \((8.75,13)\) и \((-8,75,13)\),
-
в четвёртом запросе максимальное расстояние будет достигаться между точками с номерами 3 и 7, их координаты будут равны \((10.5,13)\) и \((-10.5,13)\).
Тесты к этой задаче состоят из 9 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
«Случайные точки» означает, что координаты точек выбираются равновероятно на отрезке от \(-10^9\) до \(10^9\) и независимо друг от друга.
| Доп. ограничения | |||||||
| Группа | Баллы | \(n_i\) | \(N\) | \(q_i\) | \(Q\) | Необходимые группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия |
| 1 | 12 | \(n_i \le 10\) | \(N \le 2000\) | \(q_i \le 10\) | \(Q \le 2000\) | 0 | |
| 2 | 9 | \(n_i \le 2000\) | \(N \le 2000\) | \(q_i \le 2000\) | \(Q \le 2000\) | 0 – 1 | |
| 3 | 13 | \(n_i \le 5000\) | \(N \le 5000\) | \(q_i \le 10\,000\) | \(Q \le 10\,000\) | 0 – 2 | |
| 4 | 11 | \(n_i \le 100\,000\) | \(N \le 100\,000\) | \(q_i \le 100\,000\) | \(Q \le 100\,000\) | – | Случайные точки |
| 5 | 8 | – | – | – | – | 4 | Случайные точки |
| 6 | 12 | \(n_i \le 5000\) | \(N \le 5000\) | \(q_i \le 100\,000\) | \(Q \le 100\,000\) | 0 – 3 | |
| 7 | 11 | \(n_i \le 5000\) | \(N \le 5000\) | – | – | 0 – 3, 6 | |
| 8 | 10 | \(n_i \le 100\,000\) | \(N \le 100\,000\) | \(q_i \le 100\,000\) | \(Q \le 100\,000\) | 0 – 4, 6 | |
| 9 | 14 | – | – | – | – | 0 – 8 | Offline-проверка |
2 0 5 2 0 0 1 1 0 2 -1 3 0 4 1 2.5 8 4 0 0 6 11 7 13 4 14 0 15 -4 14 -7 13 -6 11 2 1 1.25 1.5
4.000000 5.385165 28.000000 15.000000 17.500000 21.000000