(1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100)
n
, m
으로 반복문 돌린다면, 최악의 경우 500,000 x 500,000 x 100을 탐색해야한다. (트램폴린 놓는 경우의 수 x 별 하나씩 계산)k
로 반복문을 돌려 100 x 100 x 100으로 탐색할 수 있다.public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
int l = Integer.parseInt(line[2]);
int k = Integer.parseInt(line[3]);
int[][] stars = new int[k][2];
for (int i = 0; i < k; i++) {
line = br.readLine().split(" ");
stars[i] = new int[]{Integer.parseInt(line[0]), Integer.parseInt(line[1])};
}
int answer = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
int ct = 0;
int tx = stars[i][0];
int ty = stars[j][1];
for (int[] star : stars) {
if (!isBound(tx, ty, star[0], star[1], l)) {
ct++;
}
}
answer = Math.min(ct, answer);
}
}
System.out.println(answer);
}
public static boolean isBound(int tx, int ty, int sx, int sy, int l) {
return sx >= tx && sx <= tx + l && sy >= ty && sy <= ty + l;
}
}