만드는 중입니다

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

문진

시간 제한2초메모리 제한1024 MB

요약
각 페이퍼웨이트에서 무게중심이 0.2만큼 움직여도 안정한 바닥 면을 가려내고, 그 면을 바닥에 놓았을 때 칩 높이의 최솟값과 최댓값을 구합니다.
난이도

어려움10점 중 8점

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

문제

귀사는 예술적인 문진을 만든다. 각 문진은 한 면을 공유하는 두 사면체의 합집합이다. 문진은 색이 있는 작은 알갱이가 박힌 투명한 유리 덩어리다. 각 문진에 박힌 작은 알갱이 중 하나는 사실 아주 작은 RFID 칩이다. 이 칩은 연동된 컴퓨터 가까이에 있어야 그 컴퓨터가 작동한다. 보통은 문진을 컴퓨터 위에 올려놓는다. 그러나 칩의 인식 범위에는 한계가 있으므로 칩과 평평한 컴퓨터 상판 사이의 거리가 중요하다. 따라서 문진이 충분히 안정적인 자세에 있을 때 칩과 컴퓨터 상판 사이 거리의 최솟값과 최댓값을 계산해야 한다. 무게중심을 어느 방향으로든 0.2까지 옮겨도 문진이 움직이지 않으면 그 자세는 충분히 안정적이라고 한다. 문진의 밀도는 균일하고, 칩은 점으로 볼 수 있을 만큼 작다고 가정해도 된다.

그림 10그림 11

예를 들어, 공통 면의 꼭짓점이 A = (0, 0, 0), B = (9, 0, 0), C = (0, 8, 0)이고, 한 사면체의 네 번째 꼭짓점이 D = (0, 0, 9), 다른 사면체의 네 번째 꼭짓점이 E = (1, 1, -8), 칩이 F = (1, 2, -1)에 있는 문진을 생각하자. (그림 10에서 칩은 빨간 점으로 표시되어 있다.) 문진의 면 BCD가 컴퓨터 상판에 닿도록 놓으면 최대 거리는 약 3.7이 된다(그림 11의 위쪽). 면 ACD가 컴퓨터 상판에 닿도록 놓으면 최소 거리는 1.0이 된다(그림 11의 아래쪽). 면 ACE가 컴퓨터 상판에 닿도록 놓으면 거리는 0.9에 불과하지만 충분히 안정적이지 않다.

입력

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 여섯 점 A, B, C, D, E, F를 이 순서대로 적은 한 줄이다. 각 점의 좌표는 세 정수 x, y, z로 주어진다. 두 사면체의 부피는 모두 0보다 크고, D와 E는 점 A, B, C가 정하는 평면의 서로 반대편에 있으며, 점 F는 문진의 내부에 있다. 각 좌표의 절댓값은 1000 이하이다. 문진을 충분히 안정적인 자세로 놓을 수 있는 경우가 항상 하나 이상 존재한다.

입력은 정수 0만 있는 줄로 끝난다.

출력

각 테스트 케이스마다 문진이 충분히 안정적일 때 칩에서 바닥면까지의 거리의 최솟값과 최댓값을 케이스 번호 뒤에 이어서 출력한다. 두 수는 소수점 아래 다섯 자리까지 반올림하여 출력한다. 출력 형식은 샘플 출력을 따른다.

예제1

  1. 예제 1

    입력
    0 0 0 9 0 0 0 8 0 0 0 9 1 1 -8 1 2 -1
    0 0 0 7 0 0 0 7 0 0 0 7 -1 -2 -3 2 2 2
    1 2 3 6 2 3 -2 6 3 -1 0 7 4 1 -2 -1 5 3
    0
    
    예상 출력
    Case 1: 1.00000 3.73526
    Case 2: 0.57735 2.66967
    Case 3: 0.28214 5.00871