Guest User

Solution

a guest
Nov 19th, 2013
347
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.40 KB | None | 0 0
  1. The basic idea is to apply the separating plane theorem -- if two points have line-of-sight then there is at least one tangent & normal which separates them from the circle.
  2.  
  3. Consider the set of valid normals for a given point: it forms a contiguous arc. Since two points can see each other if their sets of valid tangents intersect, the problem is equivalent to counting intersections of line segments in 1D.
Advertisement
Add Comment
Please, Sign In to add comment