금강석

지질 탐사의 결과 지하 깊숙이 묻힌 금강석 정보를 나타내는 지도가 아래 그림처럼 만들어졌다. 그림에서 굵은 점은 금강석이 위치한 곳을 나타낸다. 이제 땅을 파서 금강석을 캐려고 한다. 굴착할 영역은 항상 두 대각선이 좌표축에 평행한 정사각형 모양이다. 앞으로 이 사각형을 D-사각형이라고 부르자. 현재 보유하고 있는 예산과 굴착 기술로는 대각선의 길이가 K인 D-사각형 영역을 단 한 번만 팔 수 있다. 그래서 굴착할 D-사각형 영역에 가장 많은 금강석이 포함될 수 있도록 하려고 한다.

지도에서 가장 왼쪽 아래의 점을 좌표축의 원점 (0, 0)이라고 하자. 각 금강석은 정수 좌표에 위치한다. D-사각형의 각 꼭짓점은 정수 좌표를 가져야 하고, D-사각형의 중심, 즉, 두 대각선이 만나는 점은 반드시 지도(경계선 포함) 위에 놓여야 한다. D-사각형 변에 놓인 금강석도 이 사각형에 포함된 것으로 본다.

예를 들어, 아래 그림에서 \(K=4\)인 경우 왼쪽 D-사각형은 5개의 금강석을, 오른쪽 D-사각형은 3개의 금강석을 포함한다.

지질 탐사 지도에 대한 정보를 입력받아 가장 많은 금강석을 포함하는 D-사각형을 구하는 프로그램을 작성하라.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫째 줄에 4개의 정수 N, M, T, K가 빈칸을 사이에 두고 주어진다. N은 지도의 너비를 나타내고, M은 지도의 높이를 나타낸다\((1 \le N,\) \(M \le 1{,}000{,}000).\) T는 금강석의 개수를 나타내고, K는 D-사각형의 크기(대각선의 길이)를 나타낸다, T는 1 이상 100 이하의 정수이고, K는 2 이상 10,000,000 이하의 짝수이다. 둘째 줄부터 T개의 줄에는 각 줄마다 두 개의 정수 A와 B가 빈칸을 사이에 두고 주어진다. 여기서 (A, B)는 금강석이 위치한 곳의 좌표이다\((0 \le A \le N,\) \(0 \le B \le M).\) 입력으로 주어진 금강석의 좌표들은 모두 다르다.

첫째 줄에 D-사각형의 중심의 좌표 (X, Y)를 나타내는 두 개의 정수 X, Y를 빈칸을 사이에 두고 출력한다. 둘째 줄에는 이 D-사각형에 포함되는 금강석의 개수를 출력한다. 답이 여러 개 있는 경우에는 그 중 하나만 출력하라.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2009 > 1차 대회 > 중등부 4번