結果

問題 No.199 星を描こう
ユーザー lam6er
提出日時 2025-03-20 20:36:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 1,027 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 53,984 KB
最終ジャッジ日時 2025-03-20 20:37:32
合計ジャッジ時間 2,025 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def convex_hull(points):
    points = list(map(tuple, points))
    n = len(points)
    if n == 0:
        return []
    points = sorted(set(points))
    if n == 1:
        return points

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    full_hull = lower[:-1] + upper[:-1]
    return [tuple(x) for x in full_hull]

def main():
    import sys
    input = sys.stdin.read().split()
    points = []
    for i in range(5):
        x = int(input[2*i])
        y = int(input[2*i +1])
        points.append((x, y))
    hull = convex_hull(points)
    if len(hull) ==5:
        print("YES")
    else:
        print("NO")

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