만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

삼각형

시간 제한1초메모리 제한2048 MB

요약
정수 좌표 삼각형의 각 변에서 격자점을 하나씩 골라 만든 삼각형 넓이의 최댓값과 최솟값을 2배로 구합니다. 격자점이 없는 변이 있으면 -1을 출력합니다.
난이도

보통10점 중 5점

유형
정수론, 기하, 수학
정답자
아직 제출이 없습니다

문제

좌표가 모두 정수인 삼각형이 있다. 이 삼각형의 세 꼭짓점 AA, BB, CC의 좌표는 모두 정수이다. 삼각형의 각 변 위에서 좌표가 정수인 점을 하나씩 골라 연결하면 새로운 삼각형이 만들어진다. 이때 주어진 삼각형의 꼭짓점은 새 삼각형의 꼭짓점으로 고를 수 없다.

어떤 점을 고르느냐에 따라 새 삼각형의 넓이가 커지기도 하고 작아지기도 한다. 그런 삼각형이 존재하는 경우에 한해, 새 삼각형의 넓이가 가장 큰 경우와 가장 작은 경우를 구하는 프로그램을 작성하라.

예를 들어 아래 그림과 같이 주어진 삼각형의 세 꼭짓점이 (4,8)(4, 8), (−8,−1)(-8, -1), (7,−7)(7, -7)이면, 조건을 만족하는 삼각형 중 그림 L.1(a)의 노란색 삼각형이 넓이가 가장 크고, 그림 L.1(b)의 파란색 삼각형이 넓이가 가장 작다.

주어진 삼각형의 어느 변 위에도 좌표가 정수인 점이 없을 수 있으며, 이때는 찾는 삼각형이 존재하지 않는다.

주어진 세 점은 한 직선 위에 있지 않다는 것이 보장된다.

입력

첫째 줄에 여섯 정수 AxA_x, AyA_y, BxB_x, ByB_y, CxC_x, CyC_y가 순서대로 주어진다. 이는 각각 꼭짓점 A=(Ax,Ay)A = (A_x, A_y), B=(Bx,By)B = (B_x, B_y), C=(Cx,Cy)C = (C_x, C_y)의 좌표이다. 각 좌표값은 −109-10^9 이상 10910^9 이하의 정수이다.

출력

새로 만든 삼각형 중 넓이가 가장 큰 삼각형의 넓이를 Smax⁡S_{\max}, 가장 작은 삼각형의 넓이를 Smin⁡S_{\min}이라 하자. 그런 삼각형이 존재하면 2Smax⁡2S_{\max}와 2Smin⁡2S_{\min}을 이 순서대로 출력한다. 두 값은 모두 양의 정수이다. 그런 삼각형이 존재하지 않으면 -1을 출력한다.

예제3

  1. 예제 1

    입력
    4 8 -8 -1 7 -7
    
    예상 출력
    69 46
    
  2. 예제 2

    입력
    -8 1 7 11 7 -5
    
    예상 출력
    121 23
    
  3. 예제 3

    입력
    0 0 1 10 10 0
    
    예상 출력
    -1