Crossing Prisms

Time limit1sMemory limit128 MB

Summary
Compute the surface area of the solid formed by intersecting two identical prisms (one along the x-axis, one along the y-axis) whose cross section is a given simple polygon.
Level

Hard9 of 10

Topics
Geometry, Math, Implementation
Solved
No attempts yet

Problem

A mathematician who is also a sculptor creates sculptures out of mathematics. His method is unusual: he takes two identical prisms, crosses them at right angles, and keeps their intersection as a new polyhedron. Because he finishes each piece with paint, he needs the surface area of the polyhedron to estimate how much pigment is required.

For example, two particular identical prisms crossed at right angles produce an intersection whose surface area is approximately 194.8255.

Given the shape of the common cross section of the two identical prisms, compute the surface area of the resulting sculpture.

Input

The input consists of multiple datasets, followed by a single line containing only a zero. The first line of each dataset contains an integer nn, the number of the following lines; each of those lines contains two integers aia_i and bib_i (i=1,…,ni = 1, \dots, n).

The closed path formed by the points (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) is the outline of the cross section of the prisms. This closed path is simple: it neither crosses nor touches itself. The right-hand side of the directed segment from (ai,bi)(a_i, b_i) to (ai+1,bi+1)(a_{i+1}, b_{i+1}) is the inside of the section.

You may assume that 3≤n≤43 \le n \le 4, 0≤ai≤100 \le a_i \le 10, and 0≤bi≤100 \le b_i \le 10 (i=1,…,ni = 1, \dots, n).

One prism is placed along the xx-axis so that the outline of its cross section at x=ξx = \xi is given by the points (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). The other prism is placed along the yy-axis so that its cross section at y=ηy = \eta is given by the points (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).

Output

For each dataset, print a single line containing the surface area of the polyhedron defined by that dataset, rounded to exactly four digits after the decimal point.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    194.8255
    194.8255
    600.0000
    341.4214
    42.9519
    182.5141
    282.8427
    149.2470