結果

問題 No.3154 convex polygon judge
ユーザー nikoro256
提出日時 2025-05-20 21:52:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 207 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 53,504 KB
最終ジャッジ日時 2025-05-20 21:52:20
合計ジャッジ時間 4,591 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8


def signed_area(p1, p2, p3):
    '''符号付き面積を計算 '''
    
    area = (((p2[0] - p1[0]) * (p3[1] - p1[1])) - ((p3[0] - p1[0]) * (p2[1] - p1[1]))) / 2
    return area


def convex_hull(p_list):
    '''グラハムの凸包走査 '''

    p_sort = []
    for i in p_list:
        p_sort.append(i[0])

    # x座標が最小のものをリストの先頭に配置。
    min_index = p_sort.index(min(p_sort))
    min_p = p_list.pop(min_index)
    p_list.insert(0, min_p)

    # 座標最小の点と他の点との角度順にソート ソートアルゴリズムに選択の余地が有る。
    p_length = len(p_list)
    count = 0
    index = 0
    while True:
        count += 1
        index += 1

        area_sign = signed_area(p_list[0], p_list[index], p_list[index + 1])

        # 符号付き面積が負ならば点を入れ替え
        if area_sign < 0:
            p_list[index], p_list[index + 1] = p_list[index + 1], p_list[index]
            count = 0

        if count == p_length - 1:
            break

        if index == p_length - 2:
            index = 0

    # 凹部の点を削除する。
    index = -1
    count = 0
    while True:
        index += 1
        count += 1

        area_sign = signed_area(p_list[index], p_list[index + 1], p_list[index + 2])
        if area_sign < 0:
            del p_list[index + 1]
            count = 0

        if count == len(p_list):
            break

        if index >= len(p_list) - 3:
            index = -1
    return p_list

N=int(input())
l = []
for _ in range(N):
    X,Y=map(int,input().split())
    l.append((X,Y))
l = convex_hull(l)
if len(l) != N:
    print("No")
    exit()
for i in range(N-2):
    x,y = l[i]
    x1,y1 = l[i+1]
    x2,y2 = l[i+2]
    if (x1-x)*(y2-y1) == (y1-y)*(x2-x1):
        print("No")
        exit()
print("Yes")
0