[Python] 32840번 Triangle

https://www.acmicpc.net/problem/32840

---

 

24/11/26

 

 

ICPC본선 당시에 파이썬으로 구현해서 맞은 문제다. 약간의 많은 조건 분기가 들어가는데, 이건 사람마다 갈릴 수 있는 부분이라서 구현이 어렵다고 하기에는 조금 힘들 것 같다.

---

 

문제 접근 방식:

 

 

결론적으로 이야기 하면 변 위에 있는 정수 격자점 중 꼭짓점과 가장 가까운 두 점만 보면 된다. 즉, 봐야하는 점이 변에 대해서 2개 이므로, 총 8가지 경우의 수에 대하여 브루트포스를 돌리면 된다.

 

이 이유는 아핀변환을 곰곰히 생각해보면 된다.

 

이전에 아핀변환에 관련된 문제를 내서 그런지, 이에 대한 아이디어는 금방 떠올랐다.

 

점 2개를 고정하고 하나를 움직이는건 아핀변환에 해당한다. 기존 삼각형의 넓이에서 변화가 가장 적어지려면, 즉, 넓이의 최댓값을 구하려면 꼭짓점과 가장 가까이 있는 정수 격자점으로 옮겨야 한다.

 

옮긴 뒤, 옮긴 점과 한 점을 고정해놓고 다시 변환을 진행. 그렇게 계속 하면 넓이의 최댓값은 끝점만 보면 알 수 있다는 걸 확인할 수 있다.

 

마찬가지로, 넓이의 최솟값, 즉, 기존 삼각형의 넓이에서 변화가 제일 커지려면 꼭짓점과 가장 멀리 있는 정수 격자점으로 옮겨야 한다.

 

이를 반복.

 

그래서 양 끝점만 보면 된다. 구현할 때, 변 위에 꼭짓점을 제외한 정수 격자점이 없는 경우 불가능하므로 -1을 출력하도록 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32840번 Triangle
# 기하학
import sys
input = sys.stdin.readline
from math import gcd
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def same(self, P):
        if self.x == P.x and self.y == P.y:
            return True
        else:
            return False
class NoanswerError(Exception):
    pass
def Dir_vec(P1, P2):
    return Point(P2.x - P1.x, P2.y - P1.y)
def CCW(P, Q, R):
    A, B = Dir_vec(P, Q), Dir_vec(Q, R)
    return A.x*B.y - A.y*B.x
def find_end_point(A, B):
    dx, dy = abs(B.x - A.x), abs(B.y - A.y)
    if dx == 0:
        if A.y < B.y:
            return Point(A.x, A.y+1), Point(B.x, B.y-1)
        else:
            return Point(A.x, A.y-1), Point(B.x, B.y+1)
    else:
        G = gcd(dx, dy)
        dx, dy = dx//G, dy//G
        if A.x < B.x:
            if A.y < B.y:
                return Point(A.x+dx, A.y+dy), Point(B.x-dx, B.y-dy)
            else:
                return Point(A.x+dx, A.y-dy), Point(B.x-dx, B.y+dy)
        else:
            if A.y < B.y:
                return Point(A.x-dx, A.y+dy), Point(B.x+dx, B.y-dy)
            else:
                return Point(A.x-dx, A.y-dy), Point(B.x+dx, B.y+dy)
def solve():
    try:
        L = list(map(int, input().split()))
        P = [Point(L[2*i], L[2*i+1]) for i in range(3)]
        E = []
        for i in range(3):
            E1, E2 = find_end_point(P[i], P[(i+1)%3])
            E.append(E1)
            E.append(E2)
        for e in E:
            if e.same(P[0]) or e.same(P[1]) or e.same(P[2]):
                raise NoanswerError
        E1, E2, E3 = [E[0], E[1]], [E[2], E[3]], [E[4], E[5]]
        m, M = 1_000_000_000_000_000, 0
        for b in range(8):
            i, j, k = map(int, bin(b)[2:].zfill(3))
            A = abs(CCW(E1[i], E2[j], E3[k]))
            m, M = min(A, m), max(A, M)
        print(M, m)
        return
    except NoanswerError:
        print(-1)
        return

solve()