https://www.acmicpc.net/problem/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보다 작거나 같다.
📚 입출력 예시
입력 1
6
2 3
0 0
2 0
2 3
0 3
4 0
4 3출력 1
2🗝️ 풀이
import sys
n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
points = []
for _ in range(n):
p = tuple((map(int, sys.stdin.readline().split())))
points.append(p)
points_set = set(points)
count = 0
for p in points:
w, h = p
p1 = (w + a, h)
p2 = (w, h+b)
p3 = (w+a, h+b)
if (p1 in points_set) and (p2 in points_set) and (p3 in points_set):
count += 1
print(count)- 점들의 좌표를 points 배열에 저장한다.
- points를 순회하면서 (w+a, h), (w, h+b), (w+a, h+b)가 모두 좋아면 조건에 부합하므로 count를 1씩 증가한다.
chick! chick!