AtCoder ABC 187 B – Gentle Pairs Python解説

スポンサーリンク

Gentle Pairs

xy 平面上に 1,2,…,N の番号が付けられた N 個の点があります。点 i は (xi​,yi​) にあり、N 個の点の x 座標は互いに異なります。
以下の条件を満たす整数の組 (i, j) (i < j) の個数を求めてください。

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

AtCoder Beginner Contest 「Gentle Pairs」

まず、2点の座標間を通る直線の傾きは、座標を(x1, y1),(x2, y2)とすると、
y2 – y1 / x2 – x1 で調べることができます。あとはfor文の2重ループを使い、傾きが-1以上1以下の条件を満たす、すべての座標の組み合わせを調べます。

n = int(input())
li = [list(map(int, input().split())) for _ in range(n)]

cnt = 0

for i in range(n - 1):
    for j in range(i+1, n):
        if -1 <= (li[j][1] - li[i][1]) / (li[j][0] - li[i][0]) <= 1:
            cnt += 1

print(cnt)

座標を配列liに格納したら、for文の2重ループですべての組み合わせを見ていきます。条件を満たしているかは、-1 <= (li[j][1] – li[i][1]) / (li[j][0] – li[i][0]) <= 1で調べることができます。

AtCoderB問題

Posted by cheese