테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 점 고르기 2 ======

===== 풀이 =====
  * 효율적으로 풀어야 한다면, 스위핑과 좌표압축과 레이지 세그먼트 트리 (구간 합 update + 구간 max 쿼리) 를 이용하는 전형적인 방식의O(nlogn)풀이를 쉽게 떠올릴수 있다. 하지만 접근방식이 전형적이지 구현이 간단하다는 말은 아니다..
  * n의 제한이 100밖에 안되니까 풀이가 좀 비효율적이어도 상관없다. 간단하게 구현할수 있는 방법은 다음과 같다.
  * 가장 많은 점을 포함하는 사각형을 찾는 것은, 왼쪽변에 겹치는 점이 존재하고, 위쪽변에도 겹치는 점이 존재하는 사각형들로 후보를 좁혀도 상관 없다. (가장 많은 점을 포함하는 사각형이 왼쪽 변에 겹치는 점을 포함하지 않는다면, 그 사각형을 왼쪽변에 겹치는 점이 생길때까지 오른쪽으로 평행이동 시켜도 포함하는 점의 갯수는 줄어들지 않으므로, 여전히 가장 많은 점을 포함하는 사각형이 된다)
  * 그러면 주어진 점들중에서 2개를 뽑아서 하나를 왼쪽변, 하나를 위쪽 변에 놓는다고 생각하면 총 사각형의 후보를 n^2개로 줄일수 있다. 각 사각형이 몇개의 점을 포함하는지도, 그냥 n개의 점에 대해서 다 체크하면, 총 O(n^3)에 가장 많은 점을 포함하는 사각형을 찾을수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2190. 점 고르기 2".

- Problem link: https://www.acmicpc.net/problem/2190
- Solution link: http://www.teferi.net/ps/problems/boj/2190

Tags: [brute force]
"""


def main():
    N, A, B = [int(x) for x in input().split()]
    coords = [[int(x) for x in input().split()] for _ in range(N)]

    answer = 0
    for left, _ in coords:
        for _, top in coords:
            count = sum(
                1
                for x, y in coords
                if left <= x <= left + A and top <= y <= top + B
            )
            answer = max(answer, count)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_4}}