Tutituti's blog

By Tutituti, history, 5 years ago, In English

You are given n circles (n <= 35000) and m points (m <= 35000). No pair of circles intersect each other. In one turn, you can move a point into or out of a circle, each time it costs amount of given variable which go with each circle. So which you try to find is the minimum cost to gather all point into one region which are divided by the perimeter of circles.

Absolute value of coordinate does not exceed 10^6 Featured cost of each circle does not exceed 10^6, too.

Actually this problem originates from my training test, but I cannot find any solution in contest's t. So I will be really appreciated if you consider to give me any idea.

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

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

Do you have any link of the above question?

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

    I'm pretty sure that there will be some related link but I cannot find it by myself. Sorry

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

Is each point inside at most 1 circle?

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

    it does not lie on border of any circle, and no two circle intersect but a circle can be completely contained by a larger circle. So a point can be contained by > 1 circle :3

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

Auto comment: topic has been updated by Tutituti (previous revision, new revision, compare).

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

I don't know who dug this up (as it showed in recent actions), but here's a solution: non-intersecting circles can be swept from left to right. When a circle starts, you need to insert two objects to some set: upper and lower arc. Along the sweep line, objects should be sorted by their y-intersection with sweep line (also can be done without it but it's tricky). This way you will figure out parent circle for every circle, thus getting a tree of being-inside-something. Then the task becomes something in a tree.