제출 #1357063

#제출 시각아이디문제언어결과실행 시간메모리
1357063hairePortal (BOI24_portal)Pypy 3
100 / 100
533 ms294608 KiB
from math import gcd
import sys
input = sys.stdin.readline

n = int(input())

base = [*map(int,input().split())]
vectors = []
for _ in range(n-1):
    x,y = map(int,input().split())
    vectors.append([x-base[0],y-base[1]])
    if vectors[-1][0] < 0:
        vectors[-1] = [vectors[-1][0]*-1,vectors[-1][1]*-1]

def det(a,b):
    return abs(a[0]*b[1]-a[1]*b[0])

mathgcd = gcd
def gcd(x,y):
    if x*y == 0:
        return 0
    if x< 0 or y< 0:
        return mathgcd(abs(x),abs(y))*-1
    return mathgcd(x,y)


def reduce(a,b,c):
    if det(a,b) == 0:
        return (c,[gcd(a[0],b[0]),gcd(a[1],b[1])])
    if det(a,c) == 0:
        return (b,[gcd(a[0],c[0]),gcd(a[1],c[1])])
    if det(b,c) == 0:
        return (a,[gcd(b[0],c[0]),gcd(b[1],c[1])])
    
    
    while det(b,c) != 0 and det(a,c) != 0 and det(a,b) != 0:
        s = det(b,c)//det(a,b)
        t = det(c,a)//det(a,b)
        
        c[0] += s*a[0]+t*b[0]
        c[1] += s*a[1]+t*b[1]
        a,b,c = b,c,a

    return reduce(a,b,c)

while len(vectors) > 2:
    a,b,c = vectors.pop(),vectors.pop(),vectors.pop()
    x,y = reduce(a,b,c)
    vectors.append(x)
    if vectors[-1][0] < 0:
        vectors[-1] = [vectors[-1][0]*-1,vectors[-1][1]*-1]
    vectors.append(y)
    if vectors[-1][0] < 0:
        vectors[-1] = [vectors[-1][0]*-1,vectors[-1][1]*-1]



if len(vectors) == 2:
    a = abs(vectors[0][0]*vectors[1][1]-vectors[0][1]*vectors[1][0])
    if a == 0:
        print(-1)
    else:
        print(a)
elif len(vectors) < 2:
    print(-1)

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 50%)

=======
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...