結果

問題 No.199 星を描こう
ユーザー brthyyjpbrthyyjp
提出日時 2021-09-21 10:32:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 5,002 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 83,016 KB
実行使用メモリ 55,568 KB
最終ジャッジ日時 2024-07-03 16:16:44
合計ジャッジ時間 2,242 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
54,904 KB
testcase_01 AC 38 ms
55,456 KB
testcase_02 AC 41 ms
54,072 KB
testcase_03 AC 40 ms
55,392 KB
testcase_04 AC 40 ms
53,856 KB
testcase_05 AC 39 ms
53,776 KB
testcase_06 AC 40 ms
55,356 KB
testcase_07 AC 38 ms
54,680 KB
testcase_08 AC 39 ms
54,272 KB
testcase_09 AC 38 ms
54,272 KB
testcase_10 AC 39 ms
54,984 KB
testcase_11 AC 38 ms
54,244 KB
testcase_12 AC 38 ms
54,452 KB
testcase_13 AC 38 ms
55,180 KB
testcase_14 AC 38 ms
55,296 KB
testcase_15 AC 38 ms
53,648 KB
testcase_16 AC 38 ms
54,732 KB
testcase_17 AC 38 ms
54,848 KB
testcase_18 AC 38 ms
54,240 KB
testcase_19 AC 38 ms
55,568 KB
testcase_20 AC 38 ms
54,460 KB
testcase_21 AC 38 ms
54,468 KB
testcase_22 AC 38 ms
54,876 KB
testcase_23 AC 38 ms
54,428 KB
testcase_24 AC 38 ms
54,144 KB
testcase_25 AC 38 ms
53,936 KB
testcase_26 AC 38 ms
54,332 KB
testcase_27 AC 38 ms
54,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

class Vector:
    def __init__(self, ls: list):
        self.vec = ls

    def __len__(self):
        return len(self.vec)

    def __getitem__(self, idx):
        return self.vec[idx]

    def __repr__(self):
        return f'Vector({self.vec})'

    def add(self, vec):
        assert len(self) == len(vec)
        ret = [a+b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def sub(self, vec):
        assert len(self) == len(vec)
        ret = [a-b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def mul(self, vec):
        assert len(self) == len(vec)
        ret = [a*b for a, b in zip(self.vec, vec.vec)]
        return Vector(ret)

    def scalar_mul(self, x):
        ret = [a*x for a in self.vec]
        return Vector(ret)

    def scalar_div(self, x):
        ret = [a/x for a in self.vec]
        return Vector(ret)

    def norm(self):
        return math.sqrt(sum([x*x for x in self.vec]))

def dot(a, b):
    return sum(a.mul(b))

def cross(a, b):
    #outer product of 2d vector
    assert len(a) == 2 and len(b) == 2
    first = a[0]*b[1]
    second = a[1]*b[0]
    return first-second

EPS = 10**(-9)

def ccw(p0, p1, p2):
    # p0からp1に向かうベクトルの向きに対して、p2の位置を返す
    a = p1.sub(p0)
    b = p2.sub(p0)
    if cross(a, b) > EPS:
        return 1
        #'COUNTER_CLOCKWISE'
        # p0->p1反時計回りの方向にp2
    elif cross(a, b) < -EPS:
        return -1
        #'CLOCKWISE'
        # p0->p1時計回りの方向にp2
    elif dot(a, b) < -EPS:
        return 2
        #'ONLINE_BACK'
        # p2->p0->p1の順で直線上にp2
    elif a.norm() < b.norm():
        return -2
        #'ONLINE_FRONT'
        # p0->p1->p2の順で直線上にp2
    else:
        return 0
        #'ON_SEGMENT'
        #p0->p2->p1の順で線分p0p1上にp2

def intersect(p0, p1, p2, p3):
    if ccw(p0, p1, p2) *ccw(p0, p1, p3) <= 0 and ccw(p2, p3, p0) *ccw(p2, p3, p1) <= 0:
        return True
    else:
        return False

def getDistanceLP(p0, p1, p):
    return abs(cross(p1.sub(p0), p.sub(p0)))/p1.sub(p0).norm()

def getDistanceSP(p0, p1, p):
    if dot(p1.sub(p0), p.sub(p0)) < 0:
        return p.sub(p0).norm()
    if dot(p0.sub(p1), p.sub(p1)) < 0:
        return p.sub(p1).norm()
    return getDistanceLP(p0, p1, p)

def area(polygon):
    s = 0
    for i in range(len(polygon)):
        s += cross(polygon[i-1], polygon[i])
    s /= 2
    return s

def is_convex(polygon, pi_is_ok=False):
    # 内角が180度以下のとき: pi_is_ok = True
    # 内角が180度未満のとき: pi_is_ok = False
    if not pi_is_ok:
        ccw0 = ccw(polygon[0], polygon[1], polygon[2])
        if ccw0 not in {-1, 1}:
            return False
        for i in range(len(polygon)):
            if ccw(polygon[i-2], polygon[i-1], polygon[i]) != ccw0:
                return False
        return True
    else:
        ccws = set()
        for i in range(len(polygon)):
            ccw1 = ccw(polygon[i-2], polygon[i-1], polygon[i])
            if ccw1 not in {-1, 1}:
                continue
            ccws.add(ccw1)
        if len(ccws) <= 1:
            return True
        else:
            return False

def is_contain(polygon, p):
    # 2: pがpolygonに含まれる
    # 1: pがpolygonの辺上
    # 0: それ以外
    n = len(polygon)
    in_ = False
    for i in range(n):
        a = polygon[i].sub(p)
        b = polygon[(i+1)%n].sub(p)
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS:
            return 1
        if a[1] > b[1]:
            a, b = b, a
        if a[1] < EPS and EPS < b[1] and cross(a, b) > EPS:
            in_ = not in_
    if in_:
        return 2
    else:
        return 0

def is_ccw(p0, p1, p2):
    a = p1.sub(p0)
    b = p2.sub(p0)
    if cross(a, b) > EPS:
        return True
    else:
        return False

def monotone_chain(points):
    points.sort(key=lambda x: (x[0], x[1]))
    if len(points) <= 2:
        return points
    upper_conv = [points[0], points[1]]
    # 後ろから2番目の点と後ろから1番目の点のなすベクトルに対して、新たに加える点が反時計回りだと凸にならない
    for p in points[2:]:
        while len(upper_conv) >= 2 and is_ccw(upper_conv[-2], upper_conv[-1], p):
            upper_conv.pop()
        upper_conv.append(p)
    points = points[::-1]
    lower_conv = [points[0], points[1]]
    for p in points[2:]:
        while len(lower_conv) >= 2 and is_ccw(lower_conv[-2], lower_conv[-1], p):
            lower_conv.pop()
        lower_conv.append(p)
    res = upper_conv[1:-1]+lower_conv
    # 反時計回りで出力
    return res[::-1]

points = []
for i in range(5):
    x, y = map(int, input().split())
    points.append(Vector([x, y]))
conv = monotone_chain(points)
if len(conv) != 5:
    print('NO')
    exit()
for i in range(5):
    c = ccw(conv[i-2], conv[i-1], conv[i])
    if c in {2, -2, 0}:
        print('NO')
        exit()
else:
    print('YES')
0