結果

問題 No.199 星を描こう
コンテスト
ユーザー titia
提出日時 2025-12-27 03:08:22
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 941 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 271 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2025-12-27 03:08:24
合計ジャッジ時間 2,596 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 凸包（Andrew's monotone chain）

from operator import itemgetter

N=5
P=[tuple(map(int,input().split())) for i in range(N)] # 頂点の集合

P.sort(key=itemgetter(1)) # 一番左下の点から始める。
P.sort(key=itemgetter(0))

# 上側凸包と下側凸包
Q1=[]
Q2=[]
 
def outer_product(x,y,z,w):
    return x*w-y*z
 
for x,y in P:
    while True:
        if len(Q1)<2:
            break
 
        s,t=Q1[-1]
        u,v=Q1[-2]
 
        if outer_product(u-s,v-t,x-u,y-v)<=0:
            Q1.pop()
        else:
            break
 
    Q1.append((x,y))
 
    while True:
        if len(Q2)<2:
            break
 
        s,t=Q2[-1]
        u,v=Q2[-2]
 
        if outer_product(u-s,v-t,x-u,y-v)>=0:
            Q2.pop()
        else:
            break
 
    Q2.append((x,y))


Q2.reverse()
Q=Q1+Q2[1:] # 上側凸包と下側凸包を結んで凸包が完成


QX=set(Q)

if len(QX)==5:
    print("YES")
else:
    print("NO")
0