만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

볶음밥 지키기

면접 대비

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

요약
반지름 R인 웍을 정수 좌표 (X, Y)에 놓았을 때 가장 많은 밥알을 덮는 중심 좌표를 구합니다.
난이도

쉬움10점 중 3점

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

문제

매일 배달 음식만 시켜 먹다 질린 영재는 직접 볶음밥을 해 먹기로 했습니다. 오랜만에 맛있는 냄새가 나자 신이 난 영재가 힘차게 웍질을 했고, 지금 NN개의 밥알이 흩날리고 있습니다. 밥알이 떨어지는 방향은 모두 −z-z축 방향입니다.

흥이 깨지지 않으려면 영재는 반지름 RR인 웍을 적절한 위치에 놓아 밥알을 최대한 많이 지켜야 합니다. 웍의 중심 (X,Y)(X, Y)와 ii번째 밥알의 좌표 (xi,yi)(x_i, y_i) (1≤i≤N1 \le i \le N)에 대해 (X−xi)2+(Y−yi)2≤R\sqrt{(X-x_i)^2+(Y-y_i)^2} \le R을 만족하는 밥알은 모두 지킨 것으로 봅니다. 웍의 중심 좌표 XX와 YY는 정수여야 합니다.

일촉즉발의 상황입니다. 영재의 기분을 지켜 주세요!

입력

첫째 줄에 흩날리는 밥알의 개수 NN과 웍의 반지름 RR이 주어집니다. (1≤N,R≤1001 \le N, R \le 100)

다음 NN개의 줄에 걸쳐 ii번째 밥알의 좌표 xi,yix_i, y_i가 주어집니다. (−100≤xi,yi≤100-100 \le x_i, y_i \le 100)

모든 밥알의 위치는 서로 다르며, 주어지는 수는 모두 정수입니다.

출력

XX와 YY가 모두 정수인 좌표 중에서 가장 많은 밥알을 지킬 수 있는 웍의 중심 좌표를 출력합니다. 답이 여러 개인 경우 그중 아무거나 하나를 출력합니다.

예제1

  1. 예제 1

    입력
    7 2
    1 1
    -1 1
    3 1
    1 3
    1 -1
    5 1
    5 3
    
    예상 출력
    1 1