🎩

# ABC187 B - Gentle Pairs

2021/01/15に公開

幾何

ABC187 B - Gentle Pairs

問題へのリンク

問題概要

xy 平面上に $1, 2, \dots, N$ の番号が付けられた $N$ 個の点がある。点 $i$ は $(x_i, y_i)$ にあり、 $N$ 個の点の $x$ 座標は異なる。以下の条件を満たす整数の組 $(i, j)$ $(i < j)$ の個数を求める。

点 $i$ と点 $j$ を通る直線の傾きが-1以上1以下である。

制約

$1 \leqq N \leqq 10^3$
$|x_i|, |y_i| \leqq 10^3$

ABC中の解答

２つの点を結ぶ直線の傾きが-1から1に入るかを計算した。ただし割り算を入れると誤差が生じる可能性があったので
$-1 \leqq 傾き a = (x_i - x_j) / (y_i - y_j) \leqq 1$
とせずに
$-(y_i - y_j) \leqq x_i - x_j \leqq y_i - y_j$
とif文を実装した。

N = int(input())

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

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        xi, yi = XY[i]
        xj, yj = XY[j]
        v = xi - xj
        if v < 0:
            v *= -1
        if -v <= yi - yj <= v:
            ans += 1
print(ans)

公式解法1

傾きが-1から1の範囲に入るということは $y$ の変化量の絶対値が $x$ の変化量の絶対値より小さければよいのでif文が少しだけ簡単になる。
最初の入力をタプルで持たせたことがあまりなかったのでせっかくだから練習して実装してみた。

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

ans = 0
for i in range(N):
    for j in range(i):
        if abs(A[i][1] - A[j][1]) <= abs(A[i][0] - A[j][0]):
            ans += 1
print(ans)