結果

問題 No.3154 convex polygon judge
コンテスト
ユーザー timi
提出日時 2025-05-20 21:57:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,148 bytes
コンパイル時間 447 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 107,052 KB
最終ジャッジ日時 2025-05-20 21:57:20
合計ジャッジ時間 11,980 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42 WA * 1 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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(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

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'
    break
  d.append((x,y))
print(ans)
0