Bounding Box
Time limit1sMemory limit128 MB
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 - and -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 (), the number of vertices of the polygon, followed by three pairs of real numbers giving the and coordinates of three distinct vertices of the polygon. All numbers are separated by whitespace. The input ends with a value , which must not be processed.
Output
For each test case, output one line in the form Polygon k: A, where is the test case number starting from and is the area of the smallest rectangle whose sides are parallel to the - and -axes and that covers all vertices of the polygon. Print rounded to exactly three decimal places.