結果

問題 No.3154 convex polygon judge
ユーザー timi
提出日時 2025-05-20 21:54:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,355 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 56,340 KB
最終ジャッジ日時 2025-05-20 21:54:59
合計ジャッジ時間 5,221 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 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 functools import cmp_to_key


def arg_sort(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    if x0 * y1 == x1 * y0:
        return 0
    return 1 if x0 * y1 < x1 * y0 else -1

A=[]
from collections import deque
d=deque()
N=int(input())
for i in range(N):
  x,y=map(int, input().split())
  A.append((x,y))
  
A.sort(key=cmp_to_key(arg_sort))
for a in A:
  d.append(a)
  
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