結果
問題 | No.199 星を描こう |
ユーザー |
![]() |
提出日時 | 2020-05-05 21:12:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 1,091 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-06-27 04:12:13 |
合計ジャッジ時間 | 2,095 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
def sub(p, q): return (p[0] - q[0], p[1] - q[1]) def det(p, q): """ 外積 """ return p[0] * q[1] - p[1] * q[0] def convex_hull(ps, n): # 頂点配列 ps = ps # type:list ps.sort() k = 0 qs = [None] * (n * 2) # 下側凸包の作成 for i in range(n): while k > 1 and \ det(sub(qs[k - 1], qs[k - 2]), sub(ps[i], qs[k - 1])) <= 0: # 最後の辺が上方向を向いているかチェックするイメージ k -= 1 qs[k] = ps[i] k += 1 # 上側凸包の作成 k1 = k # 右から逆に見ていく for i in range(n - 2, -1, -1): # 1つでも頂点追加してたら, 不要な頂点をチェック while k > k1 and \ det(sub(qs[k - 1], qs[k - 2]), sub(ps[i], qs[k - 1])) <= 0: k -= 1 qs[k] = ps[i] k += 1 return qs[:k] if __name__ == '__main__': pt = [[int(_) for _ in input().split()] for i in range(5)] ans = convex_hull(pt, 5) if len(ans) == 6: print('YES') else: print('NO')