UVa 10065

From Algorithmist
Jump to navigation Jump to search

10065 - Useless Tile Packers[edit]

Summary[edit]

This is a straightforward Convex Hull question.

Explanation[edit]

The area wasted is defined in the questions as the area not covered by the points but by the convex hull. So just apply the convex hull algorithm (choose one of them) and calculate the area of the convex hull and call it . Calculate the area that the points cover and call it .

The percentage of wasted space is given by

Input[edit]

5
0 0
2 0
2 2
1 1
0 2
5
0 0
0 2
1 3
2 2
2 0
0

Output[edit]

Tile #1
Wasted Space = 25.00 %

Tile #2
Wasted Space = 0.00 %