AtCoder Beginner Contest 218 D - Rectangles【Python】
https://atcoder.jp/contests/abc218/tasks/abc218_d
AtCoder ProblemsのRecommendationでDifficulty: 715、Solve Probability: 34%でした。
defaultdictで同じx座標を持つ点のy座標、同じy座標を持つ点のx座標をそれぞれ管理し、同じx座標の点から2つ選び答えを求めていきました。
解説を見たところ、左上の点と右下の点を1組ずつ見ていき対応する左下の点と右上の点があるかを判定するという解き方をしており勉強になりました。
from collections import defaultdict N = int(input()) # あるx座標をkeyとしてそのx座標である点のx座標の辞書 dx = defaultdict(list) # あるy座標をkeyとしてそのy座標である点のx座標の辞書 dy = defaultdict(list) for i in range(N): x, y = map(int, input().split()) dx[x].append(y) dy[y].append(x) ans = 0 # 確認済みのx座標 done_x = set() for x, yl in dx.items(): # 同じx座標の点から2つ選び、共通するx座標の数から # 現在確認しているもしくは過去確認済みのx座標を引いた数を数える for y1, y2 in combinations(yl, 2): ans += len(set(dy[y1]) & set(dy[y2]) - done_x) - 1 done_x.add(x) print(ans)