Bounding Box

Time limit1sMemory limit128 MB

Summary
Given three vertices of a regular n-gon, find the area of the smallest axis-aligned rectangle enclosing the whole polygon.
Level

Hard8 of 10

Topics
Geometry, Math, Binary search
Solved
No attempts yet

Problem

The Archaeologists of the Current Millennium (ACM) occasionally discover ancient artifacts buried at the vertices of a regular polygon. The constantly shifting sand dunes of the desert make excavation difficult, so as soon as three of the polygon's vertices have been uncovered, the entire polygon must be covered with protective fabric. Given three vertices of a regular polygon, find the area of the smallest axis-aligned rectangle (a rectangle whose sides are parallel to the xx- and yy-axes) that encloses all vertices of the polygon.

Input

The input consists of several test cases, each describing one polygon. A test case begins with an integer nn (3≤n≤503 \le n \le 50), the number of vertices of the polygon, followed by three pairs of real numbers giving the xx and yy coordinates of three distinct vertices of the polygon. All numbers are separated by whitespace. The input ends with a value n=0n = 0, which must not be processed.

Output

For each test case, output one line in the form Polygon k: A, where kk is the test case number starting from 11 and AA is the area of the smallest rectangle whose sides are parallel to the xx- and yy-axes and that covers all vertices of the polygon. Print AA rounded to exactly three decimal places.

Examples2

  1. Example 1

    Input
    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
    
    Expected output
    Polygon 1: 400.000
    Polygon 2: 1056.172
    Polygon 3: 397.673
    
  2. Example 2

    Input
    4
    5.00000 5.00000
    -5.00000 5.00000
    -5.00000 -5.00000
    0
    
    Expected output
    Polygon 1: 100.000