Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

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

Given circles how to count number of circle intersections?
Автор He110W012LD, история, 4 года назад, По-английски

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.

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

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

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

Obvious hint: exploit a low constraint for radius.

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

    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))

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

      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.

      → Ответить