7573번: 고기잡이

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


$O(m^3l)$

두 물고기가 그물의 가장 왼쪽과 위에 걸쳐 있다고 생각하면 직사각형 그물의 왼쪽 위 꼭지점이 결정된다. 또한, 이 때 가능한 그물 모양은 l/2-1개 있다.
모든 가능한 그물 모양에 대해 물고기가 얼마나 포함되어 있는지 확인한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int l, m, x[100], y[100], r;
int main() {
    scanf("%*d%d%d", &l, &m);
    for (int i = 0; i < m; i++) scanf("%d%d", x + i, y + i);
    for (int i = 0; i < m; i++) {
        for (int j = i; j < m; j++) {
            for (int k = 1; k < l / 2; k++) {
                int c = 0, tx = min(x[i], x[j]), ty = min(y[i], y[j]);
                for (int p = 0; p < m; p++) c += x[p] >= tx&&y[p] >= ty&&x[p] <= tx + k&&y[p] <= ty + l / 2 - k;
                r = max(r, c);
            }
        }
    }
    printf("%d", r);
    return 0;
}