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

count number of circles that have a common point
Автор pacha2880, история, 4 года назад, По-английски

could someone please help me with this problem? given n circles (n <= 500000), count the number of circles that have a common point. it's guaranteed that the circles don't overlap.

here's the complete statement: http://coj.uci.cu/24h/problem.xhtml?pid=4161〈=es

thanks in advance

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

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

I believe you can do a sweep line, maintaining circles intersecting your current line, sorted by center coordinate. When a new circle appears, just check if it has common points with the neighbors.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Don't forget to check newly adjacent circles when a circle disappears.

    Proof sketch for correctness: If two circles touch, when the sweep line goes through the point of contact, the two circles will be adjacent in the list. Thus, it suffices to only consider all pairs of circles that are adjacent in the list at some point in time.

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

    thank you very much!

    → Ответить