結果

問題 No.3154 convex polygon judge
コンテスト
ユーザー timi
提出日時 2025-05-20 21:46:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,113 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 94,140 KB
最終ジャッジ日時 2025-05-20 21:46:18
合計ジャッジ時間 4,542 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 3 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

# cross product: (b - a)×(c - a)
def cross3(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

# O(N)
def inside_convex_polygon0(p0, qs):
    L = len(qs)
    D = [cross3(qs[i-1], p0, qs[i]) for i in range(L)]
    return all(e >= 0 for e in D) or all(e <= 0 for e in D)

# O(log N)
def inside_convex_polygon(p0, qs):
    L = len(qs)
    left = 1; right = L
    q0 = qs[0]
    while left+1 < right:
        mid = (left + right) >> 1
        if cross3(q0, p0, qs[mid]) <= 0:
            left = mid
        else:
            right = mid
    if left == L-1:
        left -= 1
    qi = qs[left]; qj = qs[left+1]
    v0 = cross3(q0, qi, qj)
    v1 = cross3(q0, p0, qj)
    v2 = cross3(q0, qi, p0)
    if v0 < 0:
        v1 = -v1; v2 = -v2
    return 0 <= v1 and 0 <= v2 and v1 + v2 <= v0

qs = [(-2, 0), (0, -2), (2, 0), (0, 2)]


from collections import deque
d=deque()
N=int(input())
for i in range(N):
  x,y=map(int, input().split())
  d.append((x,y))
  
ans='Yes'
for i in range(N):
  x,y=d.popleft()
  c=inside_convex_polygon((x,y),d)
  if c==True:
    ans='No'
  d.append((x,y))
print(ans)
0