[Python/파이썬] 백준 2121번 넷이 놀기

 

2121번: 넷이 놀기

 

문제

네 사람이서 2차원 평면상의 N개의 점을 이용해서 할 수 있는 놀이가 있다. 바로 각 사람이 1개씩의 점을 적절히 선택해서 변이 x축 혹은 y축에 평행한 직사각형을 만드는 일이다. 물론 그냥 만들면 재미가 없기 때문에 가로의 길이가 A 세로의 길이가 B인 직사각형을 몇 가지나 만들 수 있는지 알아보기로 했다.

예를 들어 점이 A(0, 0), B(2, 0), C(0, 3), D(2, 3), E(4, 0), F(4, 3)의 6개가 있고, 만들고 싶은 직사각형이 가로가 2, 세로가 3인 직사각형이라면 (A, B, C, D), (B, D, E, F)의 두 가지 경우가 가능하다. 모든 경우의 수를 구해보자.

입력

첫 줄에 점들의 개수 N(5 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에 만들고 싶은 직사각형의 가로 길이 A(1 ≤ A ≤ 1,000)와 세로 길이 B(1 ≤ B ≤ 1,000)가 주어진다. 다음 N줄에 걸쳐서 점들의 좌표가 정수로 주어진다. 이 값의 범위는 -1,000,000,000이상 1,000,000,000이하이다. N개 점들의 좌표는 각각 다르다.

출력

첫 줄에 가능한 모든 경우의 수를 출력한다. 경우의 수는 231-1보다 작거나 같다.

코드

import sys
input = sys.stdin.readline

n = int(input())
a, b = map(int, input().split())
dots = []
for _ in range(n):
    x, y = map(int, input().split())
    dots.append((x, y))

dots.sort()  # 정렬


def bs(dot):
    s, e = 0, n-1
    while s <= e:
        mid = (s+e)//2
        if dots[mid] == dot:
            return True
        elif dots[mid] > dot:
            e = mid-1
        else:
            s = mid+1
    return False


cnt = 0
for dot in dots:
    left_top = (dot[0], dot[1]+b)
    right_bottom = (dot[0]+a, dot[1])
    right_top = (dot[0]+a, dot[1]+b)
    if bs(left_top) and bs(right_bottom) and bs(right_top):
        cnt += 1
print(cnt)

주어진 점들을 하나씩 사각형의 왼쪽 아래 점이라고 생각하며 나머지 사각형을 그려줄 점이 존재하는지 탐색하였다.

주어지는 점의 개수가 최대 500,000개로 순차탐색으로 점들을 찾다가는 시간초과가 발생할 것이 분명했으므로 이분탐색을 이용하여 점의 존재 유무를 확인하였다. 이분탐색을 하기 위해 미리 점들을 정렬해두었다.