問題
考えたこと
- (x, y) の座標を与えられるのでその中から 4 つ選択して x 軸、y 軸の両方と並行な長方形を作成する。
- 入力例を見る限り正方形でもいいっぽい。
- 最初は次のようなロジックで検討。
- 座標を 1 つ取得する。
- 座標の x 軸と等しい y 軸の一覧を取得。
- y 軸の一覧から x 軸の一覧を取得。
- 座標の y 軸と等しい x 軸の一覧を取得。
- x 軸の一覧から y 軸の一覧を取得。
- これで 4 点取得できるので長方形が作成できるか判定する。
- 複雑すぎて実装が面倒だったので、別の方法はないか考えた。
思いついた別の方法
- 座標を 2 点取る。これを座標 A, 座標 B とする。
- 座標 A = (xa, ya), 座標 B = (xb, yb) とすると長方形を作るためには (xa, yb) と (xb, yb) が無いと作れない。
- また (xa, yb) (xb, yb) を作成するにあたり、斜めに線が引けないと長方形が作れない。そのため xa == xb or ya == yb の場合には読み飛ばす。
- 計算量は でも十分に間に合う。
- 座標を
set
で持てば その座標が存在するかは のオーダーで取得可能。
- 4 つの点で同じ長方形を見つけてしまうため最終的に答えを 4 で割ってやれば正解。
実装
N = int(input())
point = set()
for i in range(N):
x, y = [int(x) for x in input().split()]
point.add((x, y))
ans = 0
for x, y in point:
for tx, ty in point:
if x == tx or y == ty:
continue
if (x, ty) in point and (tx, y) in point:
ans += 1
print(ans//4)