Submission #15564117


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

gauss_t = numba.types.UniTuple(i8, 2)


@njit((gauss_t, ) * 2, cache=True)
def gauss_divmod(a, b):
    """divide a by b in Gaussian integer ring Z[i]. 

    Parameters
    ----------
    a : tuple(int, int)
        Dividend gaussian integer. 
    b : tuple(int, int)
        Divisor gaussian integer. 

    Returns
    -------
    q : tuple(int, int)
        Quotient. 
    r : tuple(int, int)
        Remainder. 
    """
    ax, ay = a
    bx, by = b
    x, y = ax * bx + ay * by, -ax * by + ay * bx
    d = bx * bx + by * by
    qx = (x + d // 2) // d
    qy = (y + d // 2) // d
    rx = ax - (bx * qx - by * qy)
    ry = ay - (bx * qy + by * qx)
    return (qx, qy), (rx, ry)


@njit((gauss_t, ) * 2, cache=True)
def gauss_gcd(a, b):
    while b[0] != 0 or b[1] != 0:
        a, b = b, gauss_divmod(a, b)[1]
    return a

@njit((i8[:], ), cache=True)
def main(XY):
    X, Y = XY[::2], XY[1::2]
    N = len(X)
    if N == 1:
        return 0
    X, Y = X - X[0], Y - Y[0]
    g = 0, 0

    for i in range(N):
        g = gauss_gcd(g, (X[i], Y[i]))

    X1 = np.empty(N, np.int64)
    Y1 = np.empty(N, np.int64)
    for i in range(N):
        X1[i], Y1[i] = gauss_divmod((X[i], Y[i]), g)[0]
    K = max(X1.max() - X1.min(), Y1.max() - Y1.min()) + 1
    return K * K - N

XY = np.array(read().split(), np.int64)[1:]

print(main(XY))

Submission Info

Submission Time
Task L - 机のしみ
User maspy
Language Python (3.8.2)
Score 12
Code Size 1609 Byte
Status
Exec Time 542 ms
Memory 120520 KB

Judge Result

Set Name Score / Max Score Test Cases
All 12 / 12 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt
Case Name Status Exec Time Memory
000.txt 509 ms 106456 KB
001.txt 495 ms 106316 KB
002.txt 538 ms 119248 KB
003.txt 491 ms 106876 KB
004.txt 536 ms 119796 KB
005.txt 494 ms 106472 KB
006.txt 535 ms 119848 KB
007.txt 494 ms 106512 KB
008.txt 538 ms 119956 KB
009.txt 496 ms 106220 KB
010.txt 535 ms 119492 KB
011.txt 499 ms 106260 KB
012.txt 535 ms 119948 KB
013.txt 498 ms 106308 KB
014.txt 542 ms 119848 KB
015.txt 509 ms 106172 KB
016.txt 540 ms 119764 KB
017.txt 494 ms 106308 KB
018.txt 539 ms 120428 KB
019.txt 489 ms 106528 KB
020.txt 534 ms 120448 KB
021.txt 494 ms 106996 KB
022.txt 530 ms 120520 KB
023.txt 491 ms 106276 KB
024.txt 511 ms 113204 KB
025.txt 500 ms 106992 KB
026.txt 497 ms 106532 KB
027.txt 495 ms 106472 KB
028.txt 492 ms 106276 KB
029.txt 491 ms 107040 KB
030.txt 494 ms 106876 KB