041 - Piles in AtCoder Farm（★7） https://atcoder.jp/contests/typical90/tasks/typical90_ao

typical90_ao.py

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __lt__(self, other):
        if self.x < other.x:
            return True
        if self.x > other.x:
            return False
        if self.y < other.y:
            return True

    def crs(self, other):
        return self.x * other.y - self.y * other.x


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b


# Step #1. 入力
N = int(input())
G = []
for _ in range(N):
    x, y = map(int, input().split())
    G.append(Point(x, y))
G.sort()

# Step #2. 凸包を求める
G1 = G[0:2]
G2 = G[0:2]
for i in range(2, N):
    while len(G1) >= 2 and (G1[-1] - G1[-2]).crs(G[i] - G1[-1]) <= 0:
        G1.pop()
    while len(G2) >= 2 and (G2[-1] - G2[-2]).crs(G[i] - G2[-1]) >= 0:
        G2.pop()
    G1.append(G[i])
    G2.append(G[i])

Totshuhou = []
for i in range(len(G1)):
    Totshuhou.append(G1[i])
for i in range(len(G2) - 2, 0, -1):
    Totshuhou.append(G2[i])

# Step #3. 辺上の格子点の数を求める
EdgePoint = len(Totshuhou)
for i in range(len(Totshuhou)):
    ax, ay = (
        Totshuhou[(i + 0) % len(Totshuhou)].x,
        Totshuhou[(i + 0) % len(Totshuhou)].y,
    )
    bx, by = (
        Totshuhou[(i + 1) % len(Totshuhou)].x,
        Totshuhou[(i + 1) % len(Totshuhou)].y,
    )
    vx = abs(bx - ax)
    vy = abs(by - ay)
    r = gcd(vx, vy)
    EdgePoint += r - 1

# Step #4. 多角形の面積(を2倍した値)を求める
Area = 0
for i in range(len(Totshuhou)):
    ax, ay = (
        Totshuhou[(i + 0) % len(Totshuhou)].x,
        Totshuhou[(i + 0) % len(Totshuhou)].y,
    )
    bx, by = (
        Totshuhou[(i + 1) % len(Totshuhou)].x,
        Totshuhou[(i + 1) % len(Totshuhou)].y,
    )
    Area += (bx - ax) * (by + ay)
Area = abs(Area)

# Step #5. 答えを求める
Answer = Area + EdgePoint + 2
print(Answer // 2 - N)