Блог пользователя otero1991

Another Geometry Problem?
Автор otero1991, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

→ Ответить