가장 낮은 피라미드
시간 제한30초메모리 제한128 MB
정수 좌표 밑면 삼각형이 주어질 때, 펼친 전개도의 정수 좌표 꼭짓점들을 선택해 접었을 때 높이가 최소가 되는 사면체를 구하거나 불가능하면 -1을 출력하는 문제입니다.
문제
모눈이 그려진 공작용 종이로 삼각뿔(사면체)을 만들려고 합니다. 밑면과 세 옆면은 모두 삼각형입니다. 종이 위에 밑면 삼각형과, 그 밑면의 세 변에 각각 이어 붙은 세 옆면 삼각형을 그린 뒤, 바깥쪽 여섯 개의 변을 따라 잘라내고, 밑면의 세 변을 접어 올려 삼각뿔로 조립합니다.
밑면 세 꼭짓점의 좌표가 주어질 때, 나머지 세 꼭짓점(세 옆면 각각의 꼭대기 점)의 좌표를 정해야 합니다. 여섯 꼭짓점의 , 좌표는 모두 이상 이하의 정수여야 합니다. 이 조건을 만족하면서 조립된 삼각뿔의 높이를 최소로 만드는 것이 목표입니다.
입력
입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식의 한 줄입니다.
X0 Y0 X1 Y1 X2 Y2
여섯 값은 모두 이상 이하의 정수입니다. , , 는 밑면 삼각형의 세 꼭짓점을 반시계 방향 순서로 나타낸 좌표입니다.
입력의 끝은 공백으로 구분된 여섯 개의 (0 0 0 0 0 0) 한 줄로 표시됩니다.
출력
각 데이터셋마다 답을 한 줄에 하나씩 출력합니다.
좌표가 모두 이상 이하의 정수가 되도록 세 점 , , 를 고를 수 있고, 네 삼각형 ––, ––, ––, –– 가 -평면에서 서로 겹치지 않으며, 이들을 접어 높이가 양수(0이 아님)인 삼각뿔로 조립할 수 있다면, 그러한 삼각뿔들 중 최소 높이를 출력합니다. 그러한 삼각뿔을 만들 수 없다면 을 출력합니다.
높이가 양수라면 그 값은 항상 이상임이 보장됩니다. 높이는 유효숫자 6자리로 출력합니다(C 언어의 %g 형식과 동일: 예를 들어 값이 이면 2, 이면 1.49666).