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

Задача . E. Сумма пересечений

Задача

У Геноса есть n различных прямых на Декартовой плоскости. Обозначим как $\text{[math]}$ список всех точек пересечения данных прямых. Каждая точка появляется в списке столько раз, сколько пар прямых в ней пересекаются. Порядок точек в списке значения не имеет.

Для некоторой точки (p, q) обозначим как $\text{[math]}$ список расстояний от соответствующих точек в $\text{[math]}$ до точки (p, q). Под расстоянием здесь имеется в виду Евклидово расстояние. На всякий случай напомним, что Евклидово расстояние между двумя точками (x₁, y₁) и (x₂, y₂) равно $\text{[math]}$ .

Теперь Геносу дана точка (p, q) и положительное целое число m. Его просят найти сумму m минимальных элементов в $\text{[math]}$ . Не следует рассматривать только уникальные элементы, то есть каждое число может войти в ответ столько раз, сколько оно встречается в $\text{[math]}$ . Генос боится задач Div1 E, поэтому попросил вас помочь ему.

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

В первой строке входных данных записано единственное число n (2 ≤ n ≤ 50 000) — количество прямых.

Вторая строка содержит три целых числа x, y и m (|x|, |y| ≤ 1 000 000, $\text{[math]}$ ) — закодированные координаты точки запроса, и целое число m, описанное в условии выше. Точка запроса (p, q) равна $\text{[math]}$ . Иными словами, разделите x и y на 1000, чтобы получить вещественную точку запроса. $\text{[math]}$ означает длину списка $\text{[math]}$ , при этом гарантируется, что $\text{[math]}$ .

В каждой из следующих n строк записано по два целых числа a_i и b_i (|a_i|, |b_i| ≤ 1 000 000) — параметры прямой $\text{[math]}$ . Гарантируется, что никакие две прямые не совпадают, то есть (a_i, b_i) ≠ (a_j, b_j) if i ≠ j.

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

Выведите единственное вещественное число — сумму m минимальных элементов $\text{[math]}$ . Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10^- 6.

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если $\text{[math]}$ .

Примечание

В первом примере три самые близкие к (1, 1) точки пересечения прямых имеют расстояния $\text{[math]}$ и $\text{[math]}$ .

Во втором примере две прямые y = 1000x - 1000 и $\text{[math]}$ пересекаются в точке (2000000, 1999999000). Расстояние от этой точки до ( - 1000, - 1000) равно $\text{[math]}$ .

Примеры

№	Входные данные	Выходные данные
1	4 1000 1000 3 1000 0 -1000 0 0 5000 0 -5000	14.282170363
2	2 -1000000 -1000000 1 1000000 -1000000 999999 1000000	2000001000.999999500
3	3 -1000 1000 3 1000 0 -1000 2000 2000 -1000	6.000000000
4	5 -303667 189976 10 -638 116487 -581 44337 1231 -756844 1427 -44097 8271 -838417	12953.274911829

time 7000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет