pacha2880's blog

count number of circles that have a common point
By pacha2880, history, 5 years ago, In English

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

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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.

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

    thank you very much!

    → Reply