結果
問題 | No.1999 Lattice Teleportation |
ユーザー | mkawa2 |
提出日時 | 2022-07-02 14:09:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 783 ms / 2,000 ms |
コード長 | 3,013 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 87,268 KB |
実行使用メモリ | 113,760 KB |
最終ジャッジ日時 | 2023-08-18 05:06:15 |
合計ジャッジ時間 | 14,572 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 76 ms
71,972 KB |
testcase_01 | AC | 78 ms
71,920 KB |
testcase_02 | AC | 71 ms
71,328 KB |
testcase_03 | AC | 75 ms
71,960 KB |
testcase_04 | AC | 77 ms
71,748 KB |
testcase_05 | AC | 105 ms
78,324 KB |
testcase_06 | AC | 100 ms
77,552 KB |
testcase_07 | AC | 88 ms
76,088 KB |
testcase_08 | AC | 78 ms
71,880 KB |
testcase_09 | AC | 73 ms
71,820 KB |
testcase_10 | AC | 72 ms
72,036 KB |
testcase_11 | AC | 106 ms
78,212 KB |
testcase_12 | AC | 612 ms
108,392 KB |
testcase_13 | AC | 776 ms
110,652 KB |
testcase_14 | AC | 72 ms
71,608 KB |
testcase_15 | AC | 772 ms
113,760 KB |
testcase_16 | AC | 466 ms
96,308 KB |
testcase_17 | AC | 709 ms
109,428 KB |
testcase_18 | AC | 629 ms
102,076 KB |
testcase_19 | AC | 658 ms
105,976 KB |
testcase_20 | AC | 783 ms
113,360 KB |
testcase_21 | AC | 783 ms
110,768 KB |
testcase_22 | AC | 782 ms
113,524 KB |
testcase_23 | AC | 158 ms
79,492 KB |
testcase_24 | AC | 311 ms
89,316 KB |
testcase_25 | AC | 632 ms
105,732 KB |
testcase_26 | AC | 525 ms
100,752 KB |
testcase_27 | AC | 460 ms
96,604 KB |
testcase_28 | AC | 731 ms
111,796 KB |
testcase_29 | AC | 387 ms
92,268 KB |
testcase_30 | AC | 228 ms
83,592 KB |
testcase_31 | AC | 201 ms
81,232 KB |
testcase_32 | AC | 498 ms
98,784 KB |
ソースコード
import sys # sys.setrecursionlimit(200005) int1 = lambda x: int(x)-1 pDB = lambda *x: print(*x, end="\n", file=sys.stderr) p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr) def II(): return int(sys.stdin.readline()) def LI(): return list(map(int, sys.stdin.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LI1(): return list(map(int1, sys.stdin.readline().split())) def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def SI(): return sys.stdin.readline().rstrip() dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] # dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] # inf = (1 << 63)-1 inf = (1 << 31)-1 md = 10**9+7 # md = 998244353 class Vector: def __init__(self, x, y, init_x=1, init_y=0): self.x = x self.y = y self.norm2 = x*x+y*y self.norm = self.norm2**0.5 self.zone = 2 if x == y == 0: self.zone = -1 elif init_x*y-init_y*x > 0: self.zone = 1 elif init_x*y-init_y*x < 0: self.zone = 3 elif init_x*x+init_y*y > 0: self.zone = 0 def __repr__(self): return "({},{})".format(self.x, self.y) def __eq__(self, other): if self.zone != other.zone: return False return self.outer(other) == 0 def __lt__(self, other): if self.zone == other.zone: return self.outer(other) > 0 return self.zone < other.zone def __add__(self, other): return Vector(self.x+other.x, self.y+other.y) def __sub__(self, other): return Vector(self.x-other.x, self.y-other.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 __neg__(self): return Vector(-self.x, -self.y) def __mul__(self, val): return Vector(val*self.x, val*self.y) __rmul__ = __mul__ def __truediv__(self, val): assert val != 0 return Vector(self.x/val, self.y/val) def dot(self, v): return self.x*v.x+self.y*v.y def outer(self, v): return self.x*v.y-self.y*v.x def rot90(self): return Vector(-self.y, self.x) def area(polygon): res = 0 for i in range(len(polygon)): [x1, y1], [x2, y2] = polygon[i-1], polygon[i] res += x1*y2-x2*y1 return abs(res) from math import gcd n = II() vv = [] for _ in range(n): a, b = LI() if a == 0 and b == 0: continue v = Vector(a, b) if v.zone > 1: v = -v vv.append(v) if not vv: print(1) exit() vv.sort() # pDB(vv) n = len(vv) s = Vector(0, 0) pre = [(0, 0)] for i in range(n): s += vv[i] pre.append((s.x, s.y)) s = Vector(0, 0) pos = [] for i in range(n-1, 0, -1): s += vv[i] pos.append((s.x, s.y)) xy = pre+pos[::-1] # pDB(xy) b = 0 for i in range(len(xy)): dx = xy[i-1][0]-xy[i][0] dy = xy[i-1][1]-xy[i][1] b += gcd(dx, dy) s2 = area(xy) # pDB(b,s2) ans = (s2+b+2)//2%md print(ans)