아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Случайная задача

시간 제한6초메모리 제한1024 MB

요약
무작위로 생성된 n개의 점과 어떤 두 점의 내적값으로 만들어진 k가 주어질 때, 내적이 k가 되는 두 점의 번호를 찾는다.
난이도

보통10점 중 7점

유형
해시맵, 수학, 완전 탐색, 기하
정답자
아직 제출이 없습니다

문제

Марти решил отвлечь своего друга Алекса от мыслей о сочных стейках и развлечь его одной интересной задачкой.

Для начала, он случайно равновероятно выбрал nn точек (x_i,y_i)(x\_i, y\_i) (0≤x_i,y_i≤1090 \le x\_i, y\_i \le 10^9). Затем, он случайно равновероятно выбрал два индекса ii и jj (1≤i,j≤n1 \le i, j \le n). После чего, вычислил значение k=x_i⋅x_j+y_i⋅y_jk = x\_i \cdot x\_j + y\_i \cdot y\_j.

Теперь он дал Алексу nn точек и число kk. И просит его найти любую пару индексов aa и bb, такую что x_a⋅x_b+y_a⋅y_b=kx\_a \cdot x\_b + y\_a \cdot y\_b = k. Алексу не хочется решать эту задачу, поэтому помогите ему.

입력

В первой строке даны два целых числа nn и kk (1≤n≤200,0001 \le n \le 200\\,000, 0≤k≤2⋅10180 \le k \le 2 \cdot 10^{18}).

В следующих nn строках дано по два целых числа x_ix\_i и y_iy\_i --- координаты ii-й точки (0≤x_i,y_i≤1090 \le x\_i, y\_i \le 10^9). Гарантируется, что точки были сгенерированы случайно равновероятно.

Гарантируется, что kk было вычислено как x_i⋅x_j+y_i⋅y_jx\_i \cdot x\_j + y\_i \cdot y\_j, где ii и jj были выбраны случайно равновероятно.

출력

Выведите два целых числа aa и bb (1≤a,b≤n1 \le a, b \le n), такие что x_a⋅x_b+y_a⋅y_b=kx\_a \cdot x\_b + y\_a \cdot y\_b = k. Если подходящих ответов несколько, вы можете вывести любой.

예제2

  1. 예제 1

    입력
    1 1476978419092933556
    901418150 815121916
    
    예상 출력
    1 1
    
  2. 예제 2

    입력
    10 95652677520045149
    805513144 38998401
    16228409 266085559
    293487744 471510400
    138613792 649258082
    904651590 244678415
    443174087 503924246
    579288498 219903162
    179297759 762760972
    92837851 728185679
    983905980 299473031
    
    예상 출력
    10 2