[ABC218] D – Rectangles

問題リンク

問題

解法

左下の頂点と右上の頂点を決めると長方形が一意に定まることを利用します。まず、左下の頂点と右上の頂点の組を全探索し，それぞれに対応する左上と右下の頂点がN個の点に含まれるかを判定します。ある点が N個の点に含まれているかの判定は、事前に点をソートしておくことで、二分探索を用いてO(logN)で求められます。

計算量

O(₂₀₀₀C₂ * log2000) = 15194204.016…

コード

import pdb
import math
from itertools import combinations
from bisect import bisect_left, bisect_right

N = int(input())
xy = [li_int_sp() for _ in range(N)] 
xy.sort(key = lambda x: (x[0], x[1]))
x, y = list(map(list, (zip(*xy))))
cnt = 0
for i, j in combinations(xy, 2): <- 1つ目の頂点i, 2つ目の頂点j
    if i[0] == j[0] or i[1] == j[1]: <- x座標かy座標が同じなら四角形できないのでスキップする
        continue
    k = [i[0], j[1]] <- 3つ目の頂点
    l = [j[0], i[1]]  <- 4つ目の頂点
    k_l = bisect_left(x, k[0]) <- 二分探索でkのx座標の左のインデックスを探索
    k_r = bisect_right(x, k[0]) <- 二分探索でkのx座標の右のインデックスを探索
    l_l = bisect_left(x, l[0]) <- 二分探索でlのx座標の左のインデックスを探索
    l_r = bisect_right(x, l[0]) <- 二分探索でlのx座標の右のインデックスを探索
    if k[1] in y[k_l:k_r] and l[1] in y[l_l:l_r]: <- 上で決めたレンジにy座標が存在するか見る
        cnt += 1
print(cnt//2) <- この実装だと同じ4頂点の組み合わせが2つ答えに入ってくるので出力する際に÷2する．

一言