14658번: 하늘에서 별똥별이 빗발친다

https://www.acmicpc.net/problem/14658

답에 해당하는 점들을 포함하는 정사각형의 위치를 오른쪽 위로 최대한 옮겨보면 왼쪽 변과 아래쪽 변 위에 점이 존재한다.
임의의 두 점에 대해 각각 한쪽 성분을 가져와 새로운 점을 만들고 이 점이 왼쪽 아래 꼭지점이 되는 정사각형을 가정한다.
이러한 정사각형들 안 최대 별똥별 개수를 구한다.

시간복잡도는 $O(k^3)$

#include<cstdio>
int n, m, l, k, r, x[100], y[100];
int main() {
    scanf("%d%d%d%d", &n, &m, &l, &k);
    for (int i = 0; i < k; i++) scanf("%d%d", x + i, y + i);
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            int c = 0;
            for (int t = 0; t < k; t++) c += x[i] <= x[t] && x[t] <= x[i] + l&&y[j] <= y[t] && y[t] <= y[j] + l;
            if (r < c) r = c;
        }
    }
    printf("%d", k - r);
    return 0;
}