otero1991's blog

Another Geometry Problem?
By otero1991, 12 years ago, In English

I have another geometry problem: N points on the plane are given and Q querys must be answered. Each query is about computing how many of those points lay inside a circunference. N,Q<=10^4

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There could be a lot of approaches — building sorted view of points by one or both coordinates, dividing set into square cells and then judging for each query which cells are enclosed completely etc.

Which variants you tried yourself and what difficulties you encountered?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought something like that but the problem is that the coordinates are x,y<=10^6

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No problem, compress the coordinates, and divide the set into squares using the compressed ones. The other option is using a kd-tree to store the points, to answer the queries, each time you visit a node check if its bounds cut the circle (if not exit the subtree), or if it is completely contained whitin it, then continue exploring the subtree or add all the points on the subtree.

      → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In the given constraints (N, Q <= 10^4 ) stupid solution O(Q * N) can be fast enough, don't use square root operation, compare squares of the distances.

→ Reply