SPOJ Digo Needs Guns

Can Anyone Explain me the question ?

I am not able to understand the question

Basically, given any general polygon with n sides, Digo can place his guns at any of the vertices. Consider the top view of the room, and you will get a 2-D polygon with n-sides. If a gun is positioned at any of the vertices, it can rotate through it’s interior angle, and the area swiped by a “ray” originating from this point, and ending at the first wall it encounters, is the area covered by this gun. You need to find the minimum number of guns such that in any n-gon, they cover the entire area.
The main point here is to realize that the polygon formed by the walls can be both a convex as well as a concave polygon.

1 Like

I was considering only concave polygons ! Thanks :slight_smile: