UVa 109

From Algorithmist

Contents 1 109 - SCUD Busters 2 Summary 3 Explanation 4 Input 5 Output

[edit] 109 - SCUD Busters

• http://acm.uva.es/p/v1/109.html

[edit] Summary

This is a straightforward Convex Hull problem. Given up to 20 sets of points (kingdoms) where we are to compute the convex hull (border), we are to process query points (missiles) where we mark the polygons. Calculate the sum of the area of the marked polygons.

Since the grid is small enough (bounded 500 by 500), we can also exploit this for a more naive solution.

[edit] Explanation

For each kingdom, we calculate the convex hull (the O(n²) algorithm is fast enough). Then, for each missile, we check to see if it is inside any of the kingdoms, and mark them if they are. Then, we can calculate the sum of the area of the marked polygons.

[edit] Input

12
3 3
4 6
4 11
4 8
10 6
5 7
6 6
6 3
7 9
10 4
10 9
1 7
5
20 20
20 40
40 20
40 40
30 30
3
10 10
21 10
21 13
-1
5 5
20 12

[edit] Output

70.50