結果

問題 No.3154 convex polygon judge
ユーザー norioc
提出日時 2025-05-20 22:48:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,320 ms / 2,000 ms
コード長 2,707 bytes
コンパイル時間 298 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 109,404 KB
最終ジャッジ日時 2025-06-17 17:04:16
合計ジャッジ時間 9,694 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import sqrt, sin, cos, atan2, tau


class Vec2:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return f'({self.x}, {self.y})'

    def dot(self, o):
        return self.x * o.x + self.y * o.y

    def cross(self, o):
        return self.x * o.y - self.y * o.x

    def normalized(self):
        m = self.mag()
        if m != 0 and m != 1:
            return Vec2(self.x / m, self.y / m)
        return self

    def magsq(self):
        return self.x * self.x + self.y * self.y

    def mag(self):
        return sqrt(self.magsq())

    def rotate(self, rad):
        x = self.x * cos(rad) - self.y * sin(rad)
        y = self.x * sin(rad) + self.y * cos(rad)
        return Vec2(x, y)

    def rot90ccw(self):
        return Vec2(-self.y, self.x)

    def distance(self, other) -> float:
        return (self - other).mag()

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __ne__(self, other):
        return not self.__eq__(other)

    def __lt__(self, other):
        if self.x == other.x:
            return self.y < other.y
        return self.x < other.x

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

    def __sub__(self, other):
        return Vec2(self.x - other.x, self.y - other.y)

    def __mul__(self, d):
        return Vec2(self.x * d, self.y * d)

    def __rmul__(self, d):
        return self.__mul__(d)

    def __truediv__(self, d):
        return Vec2(self.x / d, self.y / d)

    def __neg__(self):
        return Vec2(-self.x, -self.y)

    def __iadd__(self, other):
        self.x += other.x
        self.y += other.y
        return self

    def __isub__(self, other):
        self.x -= other.x
        self.y -= other.y
        return self


def convex_hull(points: list[Vec2]) -> list[Vec2]:
    """凸包を求める(反時計回りに頂点を返す)。
       cross() <= 0 を cross < 0 にすると辺上の点も凸包を構成する点に含める。
    """
    if len(points) <= 2: return points

    ps = sorted(points)
    vs = [Vec2(0, 0)] * (len(ps) * 2)
    k = 0
    for i in range(len(ps)):
        while k >= 2 and (vs[k-1] - vs[k-2]).cross(ps[i] - vs[k-1]) <= 0:
            k -= 1
        vs[k] = ps[i]
        k += 1

    t = k
    for i in range(len(ps)-2, -1, -1):
        while t < k and (vs[k-1] - vs[k-2]).cross(ps[i] - vs[k-1]) <= 0:
            k -= 1
        vs[k] = ps[i]
        k += 1

    return vs[:k-1]


N = int(input())
ps = []
for _ in range(N):
    X, Y = map(int, input().split())
    ps.append(Vec2(X, Y))


res = convex_hull(ps)
if len(res) == N:
    print('Yes')
else:
    print('No')
0