結果

問題 No.3005 トレミーの問題
コンテスト
ユーザー D M
提出日時 2025-02-05 16:53:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 80 ms / 2,000 ms
コード長 1,640 bytes
コンパイル時間 1,641 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 52,480 KB
最終ジャッジ日時 2025-02-05 16:53:51
合計ジャッジ時間 5,129 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def all_collinear(points):
    """点のリストが全て同一直線上にあるかチェックする関数"""
    if len(points) < 3:
        return True
    base = points[0]
    for i in range(1, len(points)):
        if points[i] != base:
            second = points[i]
            break
    else:
        return True  # 全て同じ点の場合
    for p in points:
        # 3点 (base, second, p) の外積が0なら共線
        if (second[0] - base[0]) * (p[1] - base[1]) - (second[1] - base[1]) * (p[0] - base[0]) != 0:
            return False
    return True

def determinant(matrix):
    """再帰的に行列式を計算する関数 (整数の4×4行列に適用)"""
    n = len(matrix)
    if n == 1:
        return matrix[0][0]
    if n == 2:
        return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]
    det_val = 0
    for c in range(n):
        # 第1行の各要素に対して余因子展開
        submatrix = [row[:c] + row[c+1:] for row in matrix[1:]]
        sign = (-1) ** c
        det_val += sign * matrix[0][c] * determinant(submatrix)
    return det_val

def main():
    # 入力を受け取る
    points = [tuple(map(int, input().split())) for _ in range(4)]
    
    # まずは共線性をチェック
    if all_collinear(points):
        print("NO")
        return

    # 各点 (x, y) に対して [x^2+y^2, x, y, 1] の行を作成
    matrix = []
    for x, y in points:
        matrix.append([x**2 + y**2, x, y, 1])
    
    # 行列式が0なら共円（退化円でない場合）と判定
    print("YES" if determinant(matrix) == 0 else "NO")

if __name__ == "__main__":
    main()
0