교차하는 각기둥

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

요약
동일한 단면을 가진 두 프리즘을 x축과 y축 방향으로 배치해 교차시켰을 때 생기는 다면체의 표면적을 구하는 문제입니다.
난이도

어려움10점 중 9점

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

문제

수학자이자 조각가인 어떤 사람이 수학을 이용해 조각품을 만든다. 그의 방식은 독특하다. 서로 합동인 두 각기둥(prism)을 준비한 뒤, 이 둘을 직각으로 교차시키고 그 교집합으로 생기는 다면체를 새로운 작품으로 삼는다. 완성한 작품에는 색을 칠하므로, 필요한 물감의 양을 어림하려면 이 다면체의 겉넓이를 알아야 한다.

예를 들어, 합동인 두 각기둥을 직각으로 교차시키면 겉넓이가 약 194.8255인 다면체가 만들어지는 경우가 있다.

두 합동 각기둥의 공통 단면 모양이 주어질 때, 만들어지는 조각품의 겉넓이를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 데이터셋으로 이루어지며, 마지막에는 00 하나만 있는 줄이 온다. 각 데이터셋의 첫 줄에는 정수 nn이 주어지는데, 이는 뒤따르는 줄의 개수이다. 그 뒤 각 줄에는 두 정수 aia_i와 bib_i가 주어진다 (i=1,…,ni = 1, \dots, n).

점 (a1,b1),(a2,b2),…,(an,bn),(an+1,bn+1)=(a1,b1)(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n), (a_{n+1}, b_{n+1}) = (a_1, b_1)을 차례로 이은 닫힌 경로가 각기둥 단면의 윤곽선이다. 이 닫힌 경로는 단순하다. 즉, 자기 자신과 교차하거나 닿지 않는다. 방향이 있는 선분 (ai,bi)(a_i, b_i)에서 (ai+1,bi+1)(a_{i+1}, b_{i+1})로 향할 때 그 오른쪽이 단면의 내부이다.

3≤n≤43 \le n \le 4, 0≤ai≤100 \le a_i \le 10, 0≤bi≤100 \le b_i \le 10 (i=1,…,ni = 1, \dots, n)이라고 가정해도 된다.

한 각기둥은 xx축을 따라 놓이며, x=ξx = \xi에서의 단면 윤곽선이 점 (xi,yi,zi)=(ξ,ai,bi)(x_i, y_i, z_i) = (\xi, a_i, b_i) (0≤ξ≤100 \le \xi \le 10, i=1,…,ni = 1, \dots, n)로 표현된다. 다른 각기둥은 yy축을 따라 놓이며, y=ηy = \eta에서의 단면이 점 (xi,yi,zi)=(ai,η,bi)(x_i, y_i, z_i) = (a_i, \eta, b_i) (0≤η≤100 \le \eta \le 10, i=1,…,ni = 1, \dots, n)로 표현된다.

출력

각 데이터셋에 대해, 그 데이터셋이 정의하는 다면체의 겉넓이를 소수점 아래 정확히 넷째 자리까지 반올림하여 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    4
    5 0
    0 10
    7 5
    10 5
    4
    7 5
    10 5
    5 0
    0 10
    4
    0 10
    10 10
    10 0
    0 0
    3
    0 0
    0 10
    10 0
    4
    0 10
    10 5
    0 0
    9 5
    4
    5 0
    0 10
    5 5
    10 10
    4
    0 5
    5 10
    10 5
    5 0
    4
    7 1
    4 1
    0 1
    9 5
    0
    
    예상 출력
    194.8255
    194.8255
    600.0000
    341.4214
    42.9519
    182.5141
    282.8427
    149.2470