시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1996 | 247 | 138 | 14.775% |
지질 탐사의 결과 지하 깊숙이 묻힌 금강석 정보를 나타내는 지도가 아래 그림처럼 만들어졌다. 그림에서 굵은 점은 금강석이 위치한 곳을 나타낸다. 이제 땅을 파서 금강석을 캐려고 한다. 굴착할 영역은 항상 두 대각선이 좌표축에 평행한 정사각형 모양이다. 앞으로 이 사각형을 D-사각형이라고 부르자. 현재 보유하고 있는 예산과 굴착 기술로는 대각선의 길이가 K인 D-사각형 영역을 단 한 번만 팔 수 있다. 그래서 굴착할 D-사각형 영역에 가장 많은 금강석이 포함될 수 있도록 하려고 한다.
지도에서 가장 왼쪽 아래의 점을 좌표축의 원점 (0, 0)이라고 하자. 각 금강석은 정수 좌표에 위치한다. D-사각형의 각 꼭짓점은 정수 좌표를 가져야 하고, D-사각형의 중심, 즉, 두 대각선이 만나는 점은 반드시 지도(경계선 포함) 위에 놓여야 한다. D-사각형 변에 놓인 금강석도 이 사각형에 포함된 것으로 본다.
예를 들어, 아래 그림에서 K=4인 경우 왼쪽 D-사각형은 5개의 금강석을, 오른쪽 D-사각형은 3개의 금강석을 포함한다.
지질 탐사 지도에 대한 정보를 입력받아 가장 많은 금강석을 포함하는 D-사각형을 구하는 프로그램을 작성하라.
첫째 줄에 4개의 정수 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가 빈칸을 사이에 두고 주어진다. 여기서 (A, B)는 금강석이 위치한 곳의 좌표이다(0 ≤ A ≤ N, 0 ≤ B ≤ M). 입력으로 주어진 금강석의 좌표들은 모두 다르다.
첫째 줄에 D-사각형의 중심의 좌표 (X, Y)를 나타내는 두 개의 정수 X, Y를 빈칸을 사이에 두고 출력한다. 둘째 줄에는 이 D-사각형에 포함되는 금강석의 개수를 출력한다. 답이 여러 개 있는 경우에는 그 중 하나만 출력하라.
10 8 9 4 2 2 3 4 9 3 9 5 8 2 4 5 4 3 5 3 6 4
5 4 5
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2009 > 중등부 2번