Problem B
Surveillance Squared

Many cities are setting up surveillance networks to combat crime. Each network contains many cameras, which are located at various places and which point in various directions. Each camera has a viewing angle of $90$ degrees total ($45$ degrees on each side of the center view). This means that some cameras may be able to see other cameras in its field of view. Cities would like to know which cameras can see other cameras for the purposes of planning and monitoring. Write a program that solves this problem.

\includegraphics[width=0.3\textwidth ]{surveillance}
Figure 1: This graph shows the first sample input.


Input contains up to $200$ surveillance networks. Each network starts with an integer $1 \le n \le 100$ indicating the number of cameras in the network. The following $n$ lines each describe one camera. Each camera description is given as four integers $x~ y~ a~ b$, where each is in the range $[-100,100]$. The described camera is located at $(x,y)$ and is pointing in the direction of the vector connecting the origin with location $(a,b)$. It is never the case that both $a$ and $b$ are zero. Also, no two cameras have the same location. Input ends at end of file.


For each surveillance network, for each camera, output how many other cameras it can see, in the order the cameras are listed in the input. Assume that each camera can see infinitely far, and that there is nothing blocking the view of any camera. If a camera is just on the edge of the field of view of another camera (i.e. $45$ degrees off the center view), then it should be considered as being visible by the second camera. Use a blank line between each pair of networks.

Sample Input 1 Sample Output 1
2 3 -4 2
-4 -1 2 3
-4 5 2 0
-11 2 -5 -4
-19 -9 -7 -18
-19 24 19 7
-13 20 -12 20
15 -9 21 24

CPU Time limit 4 seconds
Memory limit 1024 MB
Statistics Show
Greg Hamerly
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in