Please read the new rule regarding the restriction on the use of AI tools. ×

He110W012LD's blog

Given circles how to count number of circle intersections?
By He110W012LD, history, 4 years ago, In English

Given N circles (N <= 100000) with radius <= 10 on 2d plane (-20000 <= X,Y <= 20000) I have no idea how to solve it, can someone help me T^T.

edit: count number of pairs of intersections. ps. sorry for my bad english.

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Provide the problem source. So many people ask about problems from ongoing contests and tests...

Obvious hint: exploit a low constraint for radius.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    sorry, the problem is from this website (Thai language)

    https://beta.programming.in.th/tasks/1054

    This is my source code.

    https://pastebin.com/ykc73Mv0

    above solution is passed all test case but I think there are some case that my code doesn't work (ex. all circle are on the same X so it well be O(n^2))

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      For a circle centered at $$$(x, y)$$$, you need to iterate over $$$x_2$$$ in $$$[x-20, x+20]$$$ and $$$y_2$$$ in $$$[y-20, y+20]$$$ and then check if there's any circle centered at $$$(x_2, y_2)$$$ (use a map or unordered map). The complexity should be $$$O(N \cdot R^2)$$$, maybe multiplied by logarithm.

      → Reply