Случайная задача
Случайная задача
Марти решил отвлечь своего друга Алекса от мыслей о сочных стейках и развлечь его одной интересной задачкой.
Для начала, он случайно равновероятно выбрал n точек (xi
, yi
) (0 ≤ xi
, yi
≤ 109
). Затем, он случайно равновероятно выбрал два индекса i и j (1 ≤ i, j ≤ n). После чего, вычислил значение k = xi
* xj
+ yi
* yj
.
Теперь он дал Алексу n точек и число k. И просит его найти любую пару индексов a и b, такую что xa
* xb
+ ya
* yb
= k. Алексу не хочется решать эту задачу, поэтому помогите ему.
Входные данные
В первой строке даны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 2 * 1018
).
В следующих n строках дано по два целых числа xi
и yi
координаты i-й точки (0 ≤ xi
, yi
≤ 109
). Гарантируется, что точки были сгенерированы случайно равновероятно.
Гарантируется, что k было вычислено как xi
* xj
+ yi
* yj
, где i и j были выбраны случайно равновероятно.
Входные данные
Выведите два целых числа a и b (1 ≤ a, b ≤ n), такие что xa
* xb
+ ya
* yb
= k. Если подходящих ответов несколько, вы можете вывести любой.
1 1476978419092933556 901418150 815121916
1 1
10 95652677520045149 805513144 38998401 16228409 266085559 293487744 471510400 138613792 649258082 904651590 244678415 443174087 503924246 579288498 219903162 179297759 762760972 92837851 728185679 983905980 299473031
10 2