UVa 361

From Algorithmist
Jump to navigation Jump to search

UVA 361 - Cops and Robbers[edit]

Summary[edit]

Cops, Robbers and Civilians are placed within a world. Given the coordinates of each entity, determine the status of each civilian; it is safe if it is contained within a triangle of three cops, robbed if it is not safe and within a triangle of three robbers, and neither if otherwise.

Explanation[edit]

A citizen is safe if it is in the convex Hull formed by all cops. Cops inside that hull are irrelevant to this problem.

The convex hull formed by all robbers is also relevant. Robbers inside that hull are irrelevant to this problem.

Gotchas[edit]

What if a citizen is exactly on the line of the convex hull?

Notes[edit]

Implementations[edit]

Notes/Hints on actual implementation here.

Optimizations[edit]

Optimizations here.

Input[edit]

3 3 2
0 0
10 0
0 10
20 20
20 0
0 20
5 5
15 15
3 3 1
0 0
10 0
0 10
20 20
20 0
0 20
40 40
0 0 0

Output[edit]

Data set 1:
     Citizen at (5,5) is safe.
     Citizen at (15,15) is robbed.

Data set 2:
     Citizen at (40,40) is neither.

References[edit]