pacha2880's blog

By pacha2880, history, 10 days 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

»
10 days 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.

  • »
    »
    10 days 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.

  • »
    »
    16 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you very much!