UVa 109

From Algorithmist
Jump to navigation Jump to search

109 - SCUD Busters[edit]

Summary[edit]

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.

Explanation[edit]

For each kingdom, we calculate the convex hull (the 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.

Input[edit]

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

Output[edit]

70.50

Solutions[edit]