Extrusion

Time limit1sMemory limit128 MB

Summary

Given the vertices of a polygon in clockwise order and a volume of metal, compute the polygon's area and divide to get the bar length.

Level: Easy3 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

The Acme Extrusion Company makes steel bars with custom-designed cross-sections. To make a bar, a hole is cut into a thick metal plate; the shape of the hole is chosen by the customer.

Molten metal is then forced through the hole to form a long bar, so the shape of the hole becomes the shape of the cross-section of the bar.

Given a description of a polygonal hole and the volume of molten metal available, determine how long a bar can be formed by this process.

Input

The input contains one or more data sets. Each data set consists of the following information:

An integer $N$ , the number of vertices of the polygon. Input ends at the first value of $N$ that is less than $3$ .
$N$ lines follow. The $i$ -th line contains two floating-point numbers $x_i$ and $y_i$ , the coordinates of one vertex of the polygon, in meters. The vertices are given in clockwise order around the perimeter of the polygon.
A single floating-point number giving the volume of molten metal available, in cubic meters.

Output

For each data set, print a single line of the form

BAR LENGTH: x

where $x$ is the maximum bar length, printed with exactly two digits after the decimal point.

Examples1

Example 1

Input

4
0.0 0.0
0.0 0.1
0.1 0.1
0.1 0.0
1.0
7
0.5 1.25
0.9 1.6
0.9 1.1
0.85 1.0
0.9 0.85
0.9 0.5
0.5 0.75
100.0
0

Expected output

BAR LENGTH: 100.00
BAR LENGTH: 318.73