Notes for Guard

Pictures are shown below for each data set where guards are successfully placed.  All sites where there are too few guards match an earlier site shown.  Where the maximum risk involves a centroid, there is a gray line between the two items with maximal risk.  The minimized maximum risk is listed, followed by possible guard coordinates that correspond to the that situation:

solution illustration 1
375.00   (5, 8) (21, 8) (15.5, 6)  as in the problem text


solution illustration 2
1250.00   (21, 8) (5, 20)

Skip same pic with too few guards


solution illustration 4
21.21  (5, 8) (11, 12) (20, 0) (22, 7)

solution illustration 5
150.00   (0, 3)

solution illustration 6
9.00   (1, 0)  The centroid is at the weighted average, not the center.

solution illustration 7
0.00   (0., 0) (10, 0)

solution illustration 8
70.71   (6, 3) (12, 9)  The second guard could move some.

solution illustration 9
141.42   (8, 5)

solution illustration 10
120.00   (4, 3) (8, 1.928571) The second point can wiggle, but not as far enough from C to reach A, so the first guard is responsible for D.  Still the second guard is close enough to the biggest value at A so that the first guard does not need to worry about it and is located at a centroid of the endpoints D and F.

solution illustration 11
10.00   (2, 0) (0, 2) (2, 2)

Skip same pic with too few guards


solution illustration 13
360.00   (2.2, 0) (9.4, 0) Both guards are at points leading to maximal risk 360 with two items.

solution illustration 14
1.99   (1, 0) (13, 0) (4.009901, 0) (7.013245, 0)  Here you need to look at the exact coordinates of the middle two guards.  The one close to E has risks 1.98 while the one near H has the maximal risks 1.99.  This one is the most time consuming, with the maximum number of guards and with the maximal number points on one corridor, leading to the maximum number of centroid points to test.

solution illustration 15
400.00   (2, 0) (9, 0)  Each of these guard points has maximum risk of 400 to one side, and could move slightly to reduce the maximum risk, but to keep K visible, at least one guard cannot move and so the maximum risk remains 400.