AtCoder-ABC218 D - Rectangles【Python解答例】

AtCoder Beginner Contest218のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 218 - AtCoder

AtCoder Beginner Contest218 D - Rectangles

D - Rectangles

問題文

2 次元平面上に N 個の相異なる点があり、1,2,…,N の番号がついています。点 i(1≤i≤N) の座標は (x i​ ,y i​ ) です。

これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか？

制約

・4≤N≤2000
・0≤x i​ ,y i​ ≤10 ^9
・(x i​ ,y i​ ) ≠ (x j​ ,y j​ ) ( i ≠ j )
・入力は全て整数である。

解答例

import bisect

n = int(input())

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

XY.sort()
X.sort()

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if XY[i][0] >= XY[j][0] or XY[i][1] >= XY[j][1]:
            continue
        tmp1 = bisect.bisect_left(X,XY[i][0])
        tmp2 = bisect.bisect_left(X,XY[j][0])
        flag = 0
        while XY[tmp1][0] == XY[i][0]:
            if XY[tmp1][1] == XY[j][1] and i < tmp1 < j:
                flag += 1
                break
            tmp1 += 1
            if tmp1 > n-1:
                break
        while XY[tmp2][0] == XY[j][0]  and i < tmp2 < j:
            if XY[tmp2][1] == XY[i][1]:
                flag += 1
                break
            tmp2 += 1
            if tmp2 > n-1:
                break
        if flag == 2:
            ans += 1

print(ans)

解説

N個の点があり、このうち4個の頂点を選んだ時にX軸やY軸に平行な長方形がいくつあるか答える問題です。

配列XYにはX座標とY座標を、配列XにはX座標のみ格納していき、ソートします。

左下の頂点をi、右上の頂点をjとして全探索しました。

長方形のときだけ調べるために頂点iが頂点jより左かつ下でなければスキップします。

頂点i , j のX座標を二分探索でしらべtmp1,2としました。

頂点iと同じX座標で、頂点jと同じY座標の頂点があればflagに1を足します。

同様に頂点jと同じX座標で、頂点iと同じY座標の頂点があればさらにflagに1を足しました。

最終的にflagが2になれば、求める長方形なのでans変数に1を足してカウントします。

すべての頂点の探索を終えた後にansを出力すればＯＫです。

ABC218の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com