Useless Tile Packer, Inc., prides itself on efficiency. As their name suggests, they aim to use less space than other companies. Their marketing department has tried to convince management to change the name, believing that “useless'' has other connotations, but has thus far been unsuccessful.
Tiles to be packed are of uniform thickness and have a simple polygonal shape. For each tile, a container is custom-built. The floor of the container is a convex polygon that has the minimum possible space inside to hold the tile it is built for.
This strategy leads to wasted space inside the container. Your job is to compute the percentage of wasted space for a given tile.
The input file consists of several data blocks. Each data block describes one tile. The first line of a data block contains an integer N ( 3<=N<=100) indicating the number of corner points of the tile. Each of the next N lines contains two integers giving the (x, y) coordinates of a corner point (determined using a suitable origin and orientation of the axes) where 0<=x, y<= 1,000. The corner points occur in the same order on the boundary of the tile as they appear in the input. No three consecutive points are collinear.
The input file terminates with a value of 0 for N.
For each tile in the input, print the percentage of wasted space rounded to two digits after the decimal point. Each output must be on a separate line.
Print a blank line after each output block.
5 0 0 2 0 2 2 1 1 0 2 5 0 0 0 2 1 3 2 2 2 0 0
Tile #1 Wasted Space = 25.00 % Tile #2 Wasted Space = 0.00 %