結果

問題 No.3154 convex polygon judge
ユーザー amesyu
提出日時 2025-05-20 21:41:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,270 ms / 2,000 ms
コード長 3,094 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 118,616 KB
最終ジャッジ日時 2025-05-20 21:41:38
合計ジャッジ時間 9,194 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

# Const
INF = int(1e9)
EPS = 1e-12

# Equation and Formula
def Equation(A, B, C):
    # Solve Ax^2 + Bx + C = 0
    if A == 0 and B == 0: return None, None
    if A == 0: return -C/B, -C/B
    D = B*B - 4*A*C
    if D < 0: return None, None
    X = (-B-D**.5)/(2*A)
    Y = (-B+D**.5)/(2*A)
    return min(X, Y), max(X, Y)

def dot3(O, A, B):
    return (A - O)*(B - O)

def cross3(O, A, B):
    return (A - O)@(B - O)

def abs2(A, B):
    C = A - B
    return C.x**2 + C.y**2


# Geometry Class
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    # Comparison Operator
    def __lt__(self, other):
        if self.x == other.x: return self.y < other.y
        return self.x < other.x
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __le__(self, other):
        return self.__lt__(self, other) or self.__eq__(self, other)

    # Operator Function
    def __neg__(self):
        return self.__class__(-self.x, -self.y)

    def __add__(self, other):
        return self.__class__(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return self.__add__(-other)
    
    def __mul__(self, other):
        # vector(x, y) dot
        return self.x*other.x + self.y*other.y

    def __matmul__(self, other):
        # vector(x, y) cross
        return self.x*other.y - other.x*self.y

    # Absolute
    def __abs__(self):
        return (self.x**2+self.y**2)**.5
    
    # To_string
    def __str__(self):
        return f"({self.x}, {self.y})"
    
    __repr__ = __str__

    # Iterator
    def __iter__(self):
        return iter([self.x, self.y])

class Circle:
    def __init__(self, p, r):
        assert r > 0
        self.p = p
        self.r = r
        # (p.x-x)^2 + (p.y-y)^2 == r^2

    def inside(self, C):
        return abs2(self.p, C) <= self.r**2 + EPS
    
    def __str__(self):
        return f"Circle[center={self.p}, radius={self.r}]"

    __repr__ = __str__


# Geomery Library
def line_cross_point(L0, L1):
    x0, y0 = L0.A; x1, y1 = L0.B
    x2, y2 = L1.A; x3, y3 = L1.B
    a0 = x1 - x0; b0 = y1 - y0
    a2 = x3 - x2; b2 = y3 - y2
    d = a0*b2 - a2*b0
    if d == 0: return None
    sn = b2 * (x2-x0) - a2 * (y2-y0)
    return Point(x0 + a0*sn/d, y0 + b0*sn/d)

def circle_common_point(C0, C1):
    a, b = C0.p; p = C0.r
    c, d = C1.p; q = C1.r
    f = (-2*a+2*c, -2*b+2*d, a**2+b**2-c**2-d**2-p**2+q**2)
    L = Line(formula=f)
    return C1.intersection_point(L)

def convex_hull(ps):
    ps.sort()
    qs = []
    n = len(ps)
    if n < 3: return ps
    for p in ps:
        while len(qs) > 1 and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross3(qs[-1], qs[-2], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs[:-1]

n = int(input())
ps = []
for i in range(n):
    x, y = map(int, input().split())
    ps.append(Point(x, y))

c = convex_hull(ps)
# print(c)
print("Yes" if len(c) == n else "No")
0