Hide

Problem B
Bounding Box

The Archeologists of the Current Millenium (ACM) now and then discover ancient artifacts located at vertices of regular polygons. (Recall that an $n$-sided regular polygon is a polygon where all $n$ sides have the same lengths, and the $n$ internal angles where two sides meet are all equal.)

The moving sand dunes of the desert render the excavations difficult and thus once three vertices of a polygon are discovered there is a need to cover the entire polygon with protective fabric.

Input

Input contains multiple test cases, at most $50$.

Each case describes one polygon. It starts with an integer $3 \le n \le 50$, the number of vertices in the polygon, followed by three pairs of real numbers giving the $x$ and $y$ coordinates of three vertices of the polygon. The coordinates have absolute value at most $1000$ and at most $5$ digits after the decimal point.

The input ends with a dummy case having $n = 0$, this case should not be processed.

Output

For each test case, output one line giving the smallest area of a rectangle which can cover all the vertices of the polygon and whose sides are parallel to the $x$ and $y$ axes. You may assume that this area is at most $100\, 000$. Your answers should have an absolute or relative error of at most $10^{-9}$.

Sample Input 1 Sample Output 1
4
10.00000 0.00000
0.00000 -10.00000
-10.00000 0.00000
6
22.23086 0.42320
-4.87328 11.92822
1.76914 27.57680
23
156.71567 -13.63236
139.03195 -22.04236
137.96925 -11.70517
0
400.0000000000
1056.1719423660
397.6729693617

Please log in to submit a solution to this problem

Log in