Edit

【pythonでABC181を解説】C - Collinearity

問題概要

問題ページ

C - Collinearity
C - Collinearity

問題ページへ移動する

問題文

無限に広い \(2\) 次元平面の上に \(N\) 個の点があります。

\(i\) 番目の点は \((x_i,y_i)\) にあります。

\(N\) 個の点の中の相異なる \(3\) 点であって、同一直線上にあるものは存在するでしょうか？

制約

  • 入力はすべて整数
  • \(3 \leq N \leq 10^2\)
  • \(|x_i|, |y_i| \leq 10^3\)
  • \(i \neq j\) ならば \((x_i, y_i) \neq (x_j, y_j)\)

問題の考察

ACコード

import sys
import collections
import math


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    xy = []
    for i in range(n):
        x, y = list(map(int, input().rstrip('\n').split()))
        xy.append([x, y])
    xy.sort()
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            x1, y1 = xy[j][0] - xy[i][0], xy[j][1] - xy[i][1]
            x1, y1 = x1 // math.gcd(x1, y1), y1 // math.gcd(x1, y1),
            for k in range(j + 1, n):
                x2, y2 = xy[k][0] - xy[j][0], xy[k][1] - xy[j][1]
                x2, y2 = x2 // math.gcd(x2, y2), y2 // math.gcd(x2, y2),
                if x1 == x2 and y1 == y2:
                    print("Yes")
                    exit()
    print("No")


if __name__ == '__main__':
    solve()

-Edit
-