結果
問題 | No.1447 Greedy MtSaka |
ユーザー | brthyyjp |
提出日時 | 2021-09-20 00:04:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,262 bytes |
コンパイル時間 | 1,015 ms |
コンパイル使用メモリ | 87,312 KB |
実行使用メモリ | 71,876 KB |
最終ジャッジ日時 | 2023-09-14 21:49:08 |
合計ジャッジ時間 | 3,442 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
71,772 KB |
testcase_01 | AC | 72 ms
71,736 KB |
testcase_02 | AC | 71 ms
71,344 KB |
testcase_03 | AC | 72 ms
71,848 KB |
testcase_04 | AC | 74 ms
71,860 KB |
testcase_05 | AC | 71 ms
71,396 KB |
testcase_06 | AC | 72 ms
71,344 KB |
testcase_07 | AC | 72 ms
71,512 KB |
testcase_08 | AC | 72 ms
71,664 KB |
testcase_09 | AC | 71 ms
71,792 KB |
testcase_10 | AC | 71 ms
71,504 KB |
testcase_11 | AC | 72 ms
71,860 KB |
testcase_12 | AC | 74 ms
71,392 KB |
testcase_13 | AC | 72 ms
71,392 KB |
testcase_14 | AC | 73 ms
71,736 KB |
testcase_15 | AC | 72 ms
71,636 KB |
testcase_16 | AC | 72 ms
71,368 KB |
testcase_17 | AC | 72 ms
71,640 KB |
testcase_18 | AC | 73 ms
71,776 KB |
testcase_19 | AC | 73 ms
71,876 KB |
ソースコード
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)