사용한 알고리즘
알고리즘 설명
- 먼저 돌이 있는 좌표를 x축 정렬을 한다.
- 정렬된 이후 첫번째 돌의 x축이 감쌀 수 있는 돌을 모두 센다.
- 이 감싸진 돌들의 y축을 모두 정렬 한다.
- 정렬된 y축 요소들은 이미 x축으로는 정사각형에 들어갈 수 있음을 안다.
- 고로 y축 중 가장 많이 포함될 수 있는 돌의 개수를 새는 것이 관건이다.
- 가장 작은 y축 부터 투포인터 형태로 시작점을 I, 도착점을 J로 두고
y[J]-y[I] <= K을 만족하는 경우 J를 증가, 위를 만족하지 않으면 I를 증가시켜 J-I의 값이 제일 커지는 지점을 결과값으로 저장한다. - J-I 값이 가장 큰 값을 가질때에 정사각형 좌표를 따로 저장한다.
- 모든 돌에 대해 이를 적용한 뒤에 결과를 출력한다.
- 모든 돌의 수가 최대 100개이므로 O(T^2log(T))도 충분하다.
풀이
// baekjoon 2492 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_T=101;
int N, M, T, K;
pair<int, int> stone[MAX_T];
int y[MAX_T], ret, ret_x, ret_y;
int main() {
scanf("%d%d%d%d", &N, &M, &T, &K);
for (int i=0; i<T; i++)
scanf("%d%d", &stone[i].first, &stone[i].second);
sort(stone, stone+T);
for (int i=0, j=0; i<T; i++) {
while (j<T && stone[j].first - stone[i].first <= K) j++;
for (int k=0; k<j-i; k++) y[k] = stone[k+i].second;
sort(y, y+j-i);
for (int I=0, J=0; I<j-i; I++) {
while (J<j-i && y[J] - y[I] <= K) J++;
if (ret < J-I) {
ret = J-I;
ret_x = min(N, stone[i].first+K)-K;
ret_y = min(M, y[I]+K);
}
}
}
printf("%d %d\n", ret_x, ret_y);
printf("%d\n", ret);
return 0;
}
