MarioYC's blog

SPOJ CIRUT
By MarioYC, 11 years ago, In English

Hi everyone,

I'm trying to solve this problem.

I recently solved problem "2361-Areas" at ZOJ, for an explanation you could see my post here.

Now I think problem CIRUT from SPOJ could be solved in a similar way since areas covered by more than one circle are convex. I still haven't thought about how to solve it for areas covered by only one circle.

The problem is that since there area about N^2 areas if I test in O(n) how many circles cover it I would get TLE. So how could I do this faster? or is there another approach to the problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Maybe we can use integration by sampling? That is, we draw many vertical lines, then for each line we find the intersection intervals on that line with each of the circle, and for that line we add to answer a value of sampling width multiplied by total intersection interval coverage on that line. I am not sure about that width, but 0.01 already may be a sufficient one, then we make 200000 lines (1000·200000 is not so bad for TL).

→ Reply