가장 낮은 피라미드

시간 제한30초메모리 제한128 MB

요약
정수 좌표 밑면 삼각형이 주어질 때, 펼친 전개도의 정수 좌표 꼭짓점들을 선택해 접었을 때 높이가 최소가 되는 사면체를 구하거나 불가능하면 -1을 출력하는 문제입니다.
난이도

어려움10점 중 9점

유형
기하, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

모눈이 그려진 공작용 종이로 삼각뿔(사면체)을 만들려고 합니다. 밑면과 세 옆면은 모두 삼각형입니다. 종이 위에 밑면 삼각형과, 그 밑면의 세 변에 각각 이어 붙은 세 옆면 삼각형을 그린 뒤, 바깥쪽 여섯 개의 변을 따라 잘라내고, 밑면의 세 변을 접어 올려 삼각뿔로 조립합니다.

밑면 세 꼭짓점의 좌표가 주어질 때, 나머지 세 꼭짓점(세 옆면 각각의 꼭대기 점)의 좌표를 정해야 합니다. 여섯 꼭짓점의 XX, YY 좌표는 모두 −100-100 이상 100100 이하의 정수여야 합니다. 이 조건을 만족하면서 조립된 삼각뿔의 높이를 최소로 만드는 것이 목표입니다.

입력

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식의 한 줄입니다.

X0 Y0 X1 Y1 X2 Y2

여섯 값은 모두 −100-100 이상 100100 이하의 정수입니다. (X0,Y0)(X_0, Y_0), (X1,Y1)(X_1, Y_1), (X2,Y2)(X_2, Y_2) 는 밑면 삼각형의 세 꼭짓점을 반시계 방향 순서로 나타낸 좌표입니다.

입력의 끝은 공백으로 구분된 여섯 개의 00 (0 0 0 0 0 0) 한 줄로 표시됩니다.

출력

각 데이터셋마다 답을 한 줄에 하나씩 출력합니다.

좌표가 모두 −100-100 이상 100100 이하의 정수가 되도록 세 점 (Xa,Ya)(X_a, Y_a), (Xb,Yb)(X_b, Y_b), (Xc,Yc)(X_c, Y_c) 를 고를 수 있고, 네 삼각형 (X0,Y0)(X_0,Y_0)–(X1,Y1)(X_1,Y_1)–(Xa,Ya)(X_a,Y_a), (X1,Y1)(X_1,Y_1)–(X2,Y2)(X_2,Y_2)–(Xb,Yb)(X_b,Y_b), (X2,Y2)(X_2,Y_2)–(X0,Y0)(X_0,Y_0)–(Xc,Yc)(X_c,Y_c), (X0,Y0)(X_0,Y_0)–(X1,Y1)(X_1,Y_1)–(X2,Y2)(X_2,Y_2) 가 XYXY-평면에서 서로 겹치지 않으며, 이들을 접어 높이가 양수(0이 아님)인 삼각뿔로 조립할 수 있다면, 그러한 삼각뿔들 중 최소 높이를 출력합니다. 그러한 삼각뿔을 만들 수 없다면 −1-1 을 출력합니다.

높이가 양수라면 그 값은 항상 0.000010.00001 이상임이 보장됩니다. 높이는 유효숫자 6자리로 출력합니다(C 언어의 %g 형식과 동일: 예를 들어 값이 22 이면 2, 1.49666…1.49666\ldots 이면 1.49666).

예제1

  1. 예제 1

    입력
    0 0 1 0 0 1
    0 0 5 0 2 5
    -100 -100 100 -100 0 100
    -72 -72 72 -72 0 72
    0 0 0 0 0 0
    
    예상 출력
    2
    1.49666
    -1
    8.52936