백준 14658 하늘에서 별똥별이 빗발친다

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

n,m의 범위가 너무 크기 때문에 배열은 만들 수 없고,
n,m크기만큼 트램펄린을 한칸씩 밀면 너무 많은 계산량이 생긴다.

처음 아이디어는 각 별을 기준으로 1,2,3,4분면을 탐색했는데,
이렇게 탐색하면 어떤 별을 꼭지점으로 하지 않는 최대값이 나올 경우 예외가 생긴다.

두 모서리에 두개의 별을 걸치고 해당 트램펄린을 기준으로 얼마나 별이 내려왔는지 구하면 된다.

import sys
input = sys.stdin.readline
n,m,l,k = list(map(int,input().split()))
stars = []
for i in range(k):
    x,y = list(map(int,input().split()))
    stars.append((x,y))
ans = -1
for i in range(len(stars)):
    for j in range(len(stars)):
        x = stars[i][0]
        y = stars[j][1]
        cnt = 0
        for k in range(len(stars)):
            nx = stars[k][0]
            ny = stars[k][1]
            if x <= nx <= x + l and y <= ny <= y + l:
                cnt += 1
        ans = max(ans,cnt)

print(len(stars) - ans)