금강석
시간 제한1초메모리 제한128 MB
좌표를 45도 회전시켜 대각선이 K인 정사각형(다이아몬드) 안에 가장 많은 점이 들어가도록 하는 중심 좌표를 찾는 문제입니다.
문제
지질 탐사 지도에는 지하에 묻힌 금강석들의 위치가 굵은 점으로 표시되어 있다. 굴착은 한 번만 할 수 있으며, 굴착 영역은 두 대각선이 각각 좌표축과 평행한 정사각형이다. 이 정사각형을 D-사각형이라고 하자. 사용할 수 있는 D-사각형의 대각선 길이는 K로 정해져 있다. D-사각형 안에 포함되는 금강석 수가 최대가 되도록 중심을 정해야 한다.
지도의 왼쪽 아래 점을 좌표축의 원점 (0, 0)으로 둔다. 모든 금강석은 정수 좌표에 있다. D-사각형의 네 꼭짓점도 정수 좌표여야 하며, 두 대각선이 만나는 중심은 지도 위 또는 경계 위에 있어야 한다. D-사각형의 변 위에 있는 금강석도 포함한다.
아래 그림에서 K=4라면 왼쪽 D-사각형은 금강석 5개를 포함하고, 오른쪽 D-사각형은 금강석 3개를 포함한다.
지질 탐사 지도 정보가 주어질 때, 포함하는 금강석 수가 최대인 D-사각형의 중심과 그 개수를 구하는 프로그램을 작성하라.
입력
첫째 줄에 네 정수 N, M, T, K가 공백으로 구분되어 주어진다. N은 지도의 너비, M은 지도의 높이이다 (1 <= N, M <= 1,000,000). T는 금강석의 개수이고, K는 D-사각형의 대각선 길이이다. T는 1 이상 100 이하의 정수이며, K는 2 이상 10,000,000 이하의 짝수이다.
둘째 줄부터 T개의 줄에는 각 금강석의 좌표를 나타내는 두 정수 A, B가 공백으로 구분되어 주어진다 (0 <= A <= N, 0 <= B <= M). 입력으로 주어지는 금강석의 좌표는 모두 다르다.
출력
첫째 줄에 선택한 D-사각형 중심의 좌표 X, Y를 공백으로 구분하여 출력한다. 둘째 줄에는 이 D-사각형에 포함되는 금강석의 개수를 출력한다.
정답이 여러 개라면 그중 아무 하나를 출력해도 된다.