プログラムのお勉強メモ

プログラムの勉強メモです. Python, Rust, など.

ABC218_D(Rectangles)

問題

考えたこと

  • (x, y) の座標を与えられるのでその中から 4 つ選択して x 軸、y 軸の両方と並行な長方形を作成する。
  • 入力例を見る限り正方形でもいいっぽい。
  • 最初は次のようなロジックで検討。
    1. 座標を 1 つ取得する。
    2. 座標の x 軸と等しい y 軸の一覧を取得。
    3. y 軸の一覧から x 軸の一覧を取得。
    4. 座標の y 軸と等しい x 軸の一覧を取得。
    5. x 軸の一覧から y 軸の一覧を取得。
    6. これで 4 点取得できるので長方形が作成できるか判定する。
  • 複雑すぎて実装が面倒だったので、別の方法はないか考えた。

思いついた別の方法

  • 座標を 2 点取る。これを座標 A, 座標 B とする。
  • 座標 A = (xa, ya), 座標 B = (xb, yb) とすると長方形を作るためには (xa, yb) と (xb, yb) が無いと作れない。
  • また (xa, yb) (xb, yb) を作成するにあたり、斜めに線が引けないと長方形が作れない。そのため xa == xb or ya == yb の場合には読み飛ばす。
  • 計算量は  N^{2} でも十分に間に合う。
  • 座標を set で持てば その座標が存在するかは  N(1) のオーダーで取得可能。
  • 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)