UVa 10065

From Algorithmist

Contents 1 10065 - Useless Tile Packers 2 Summary 3 Explanation 4 Input 5 Output

[edit] 10065 - Useless Tile Packers

• http://acm.uva.es/p/v100/10065.html

[edit] Summary

This is a straightforward Convex Hull question.

[edit] Explanation

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 A_c. Calculate the area that the points cover and call it A.

The percentage of wasted space is given by

[edit] Input

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

[edit] Output

Tile #1
Wasted Space = 25.00 %

Tile #2
Wasted Space = 0.00 %