結果

問題 No.1999 Lattice Teleportation
ユーザー tnodinotnodino
提出日時 2022-07-02 00:51:18
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,812 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 87,404 KB
実行使用メモリ 140,888 KB
最終ジャッジ日時 2023-08-17 12:39:58
合計ジャッジ時間 10,510 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
71,872 KB
testcase_01 AC 91 ms
71,636 KB
testcase_02 AC 91 ms
71,912 KB
testcase_03 AC 90 ms
72,016 KB
testcase_04 AC 104 ms
76,868 KB
testcase_05 AC 148 ms
79,108 KB
testcase_06 AC 144 ms
78,836 KB
testcase_07 AC 119 ms
76,732 KB
testcase_08 AC 107 ms
76,732 KB
testcase_09 AC 91 ms
72,092 KB
testcase_10 AC 91 ms
71,872 KB
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 712 ms
140,440 KB
testcase_14 AC 92 ms
72,116 KB
testcase_15 AC 708 ms
140,236 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 AC 713 ms
140,644 KB
testcase_21 AC 705 ms
140,888 KB
testcase_22 AC 699 ms
140,728 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd, sqrt, acos, pi
from collections import deque
mod = 10**9+7

class Point:
    def __init__(self, px, py):
        self.px = px
        self.py = py

def operator_p(a1, a2):
    return Point(a1.px + a2.px, a1.py + a2.py)

def operator_m(a1, a2):
    return Point(a1.px - a2.px, a1.py - a2.py)

def operator(a1, a2):
    if a1.px < a2.px:
        return True
    if a1.px > a2.px:
        return False
    if a1.py < a2.py:
        return True
    return False

def getangle(G):
    # 点 G の偏角を求める
    if G.py >= 0.0:
        I = G.px / sqrt(pow(G.px, 2) + pow(G.py, 2))
        kaku = acos(I) * 180.0 / pi
        return kaku
    else:
        I = G.px / sqrt(pow(G.px, 2) + pow(G.py, 2))
        kaku = acos(I) * 180.0 / pi
        return 360.0 - kaku

# 点 p1 と p2 の外積を求める
def crs(p1, p2):
    return p1.px * p2.py - p1.py * p2.px

N = int(input())
Z = []
for i in range(N):
    A,B = map(int,input().split())
    if A == 0 and B == 0:
        continue
    if B < 0:
        A *= -1
        B *= -1
    Z.append(Point(A, B))
N = len(Z)

vec = []
for i in range(N):
    SA = operator_m(Point(0, 0), Z[i])
    angle = getangle(SA)
    vec.append([angle, Z[i]])
vec.sort()

P = [Point(0, 0)]
Q = [Point(0, 0)]
x,y = 0,0
for i in range(N):
    x += vec[i][1].px
    y += vec[i][1].py
    P.append(Point(x, y))
x,y = 0,0
for i in range(N):
    x += vec[N-i-1][1].px
    y += vec[N-i-1][1].py
    Q.append(Point(x, y))

G = []
for i in range(N+1):
    G.append(P[i])
for i in range(N-1,0,-1):
    G.append(Q[i])
if len(G) == 1:
    print(1)
    exit()

G1 = deque()
G2 = deque()
Totsuhou = []
G1.append(G[0])
G2.append(G[0])
G1.append(G[1])
G2.append(G[1])
for i in range(2,len(G)):
    while len(G1) >= 2 and crs(operator_m(G1[len(G1)-1], G1[len(G1)-2]), operator_m(G[i], G1[len(G1)-1])) <= 0:
        G1.pop()
    while len(G2) >= 2 and crs(operator_m(G2[len(G2)-1], G2[len(G2)-2]), operator_m(G[i], G2[len(G2)-1])) >= 0:
        G2.pop()
    G1.append(G[i])
    G2.append(G[i])
G1 = list(G1)
G2 = list(G2)
for i in range(len(G1)):
    Totsuhou.append(G1[i])
for i in range(len(G2)-2,0,-1):
    Totsuhou.append(G2[i])

EdgePoint = len(Totsuhou)
for i in range(len(Totsuhou)):
    ax = Totsuhou[(i+0) % len(Totsuhou)].px
    ay = Totsuhou[(i+0) % len(Totsuhou)].py
    bx = Totsuhou[(i+1) % len(Totsuhou)].px
    by = Totsuhou[(i+1) % len(Totsuhou)].py
    vx = abs(bx - ax)
    vy = abs(by - ay)
    r = gcd(vx, vy)
    EdgePoint += r - 1

Area = 0
for i in range(len(Totsuhou)):
    ax = Totsuhou[(i+0) % len(Totsuhou)].px
    ay = Totsuhou[(i+0) % len(Totsuhou)].py
    bx = Totsuhou[(i+1) % len(Totsuhou)].px
    by = Totsuhou[(i+1) % len(Totsuhou)].py
    Area += (bx - ax) * (by + ay)
Area = abs(Area)

Answer = Area + EdgePoint + 2
print(Answer // 2 % mod)
0