ABC187-B Gentle Pairs 解説 - neboccoのブログ

　\(O(N \log N)\) で解きます。

問題

リンクはこちら

概要

与えられる点の集合 \(S\) の中から二点を選ぶとき、それらを結んだ直線の傾きが \(-1\) 以上 \(1\) 以下になる組み合わせはいくつあるか？

解法

　editorial解は単純にすべてのペアについて調べるだけですが、ここでは他の解き方を紹介します。

　まず、こういう図を想像します。

f:id:nebocco:20210108160250p:plain — こういうイメージ

点 \(\mathrm{P}\) と結んだ時に傾きが \(-1\) 以上 \(1\) 以下になるのは灰色で塗られた範囲です。よって、 \((\mathrm{P}, \mathrm{Q})\) は条件を満たしますが、 \((\mathrm{P}, \mathrm{R})\) は満たさないことが見て取れます。

　この図を左に \(45^\circ\) 回転してみます。

f:id:nebocco:20210108160203p:plain — 45°回転した図

\(45^\circ\) 回転した座標系を新たに考えると、問題の条件は「自分より左下、または右上にある」と言い替えることができます。

　よって、全ての点について自身の左下にいくつの点があるかを数えることで、全てのペアを重複なく数えることができます。これは、 \(X\) 座標の小さい順に点を見ていき、今見ている点より \(Y\) 座標の小さな点がこれまでにいくつあったかが計算できれば良いので、平衡二分木やFenwick Treeを使うことで \(O(N \log N)\) で解くことができます。（「平面走査」と呼ばれるテクニックです。）

class FenwickTree:
    # 実装略

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

# 座標変換
P = [(x-y, x+y) for (x, y) in P]

# 座標圧縮
def compress(p):
    x_set = sorted(set([x for (x, y) in p]))
    y_set = sorted(set([y for (x, y) in p]))
    x_dict = {x:i for i, x in enumerate(x_set)}
    y_dict = {y:i for i, y in enumerate(y_set)}
    return [(x_dict[x], y_dict[y]) for (x, y) in p]

P = compress(P)

# 平面走査
P.sort()
bit = FenwickTree(N)
ans = 0
for (_, y) in P:
    ans += bit.bitsum(y+1)
    bit.bitadd(y, 1)
print(ans)