【pythonで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 \le N \le 10^3\)
• \(|x_i|, |y_i| \le 10^3\)
• \(i \neq j\) ならば \(x_i \neq x_j\)

問題の考察

制約は\(1 \le N \le 10^3\)なので、各\(i\)と\(j\)について全検索しても十分に間に合う。

各\(2\)点の傾きは\(\displaystyle\frac{(y_j - y_i)}{(x_j - x_i)}\)で求めることができます。

\((x_j - x_i)=0\)だとエラーが発生するので注意が必要だが、今回は制約で\(i \neq j\) ならば \(x_i \neq x_j\)とあるので\((x_j - x_i)\)（分母）が\(0\)になることはない。

後は、この傾きが\(-1\) 以上 \(1\) 以下である場合にカウントした結果を出力すれば良い。

たびすけ

傾きを求める公式は覚えておきましょう！
また傾きをプログラムで求める際は分母が\(0\)にならないか確認するクセをつけましょう！

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    xy = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    cnt = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            z = (xy[i][1] - xy[j][1]) / (xy[i][0] - xy[j][0])
            if -1 <= z <= 1:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()