結果

問題 No.1447 Greedy MtSaka
ユーザー brthyyjpbrthyyjp
提出日時 2021-09-20 00:04:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 2,262 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 53,376 KB
最終ジャッジ日時 2024-07-02 04:34:59
合計ジャッジ時間 1,873 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,864 KB
testcase_01 AC 42 ms
52,992 KB
testcase_02 AC 46 ms
52,864 KB
testcase_03 AC 42 ms
52,736 KB
testcase_04 AC 41 ms
53,120 KB
testcase_05 AC 42 ms
52,992 KB
testcase_06 AC 41 ms
52,480 KB
testcase_07 AC 42 ms
52,480 KB
testcase_08 AC 42 ms
53,120 KB
testcase_09 AC 41 ms
52,736 KB
testcase_10 AC 42 ms
52,992 KB
testcase_11 AC 42 ms
52,480 KB
testcase_12 AC 42 ms
52,352 KB
testcase_13 AC 41 ms
52,992 KB
testcase_14 AC 42 ms
53,376 KB
testcase_15 AC 42 ms
53,248 KB
testcase_16 AC 42 ms
52,736 KB
testcase_17 AC 42 ms
52,992 KB
testcase_18 AC 42 ms
52,480 KB
testcase_19 AC 42 ms
52,992 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):
    a = p1.sub(p0)
    b = p2.sub(p0)
    if cross(a, b) > EPS:
        return 1 #'COUNTER_CLOCKWISE'
    elif cross(a, b) < -EPS:
        return -1 #'CLOCKWISE'
    elif dot(a, b) < -EPS:
        return 2 #'ONLINE_BACK'
    elif a.norm() < b.norm():
        return -2 #'ONLINE_FRONT'
    else:
        return 0 #'ON_SEGMENT'

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

n = int(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((Vector([x, y])))
s = area(P)
print(s)
0