Hello everyone, I recently encountered this problem in an interview.

You are given centers of n circles along with their radius. All of them are integral values. You need to find the number of integral points inside all those circles.

Note — Circles can overlap.

*n* <= 3000

Coordinates of centre <= 5*e*5

Radius <= 3000

Can anybody help me with this? I was only able to think of a brute force solution that was checking every point in that range whether it lies in any circle or not.

For every circle, suppose (x,y) is centre and r is radius. Go from (y-r) to (y+r) because that will be the range of y coordinates that can lie inside this circle. For each y, you can easily calculate the ranges of x coordinates that will lie inside this circle using simple Pythagoras theorem. Create a vector for each y coordinate, that will contain several intervals of x coordinates that circles might have. For each y while iterating for a single circle, push the range of x coordinates in y's vector. In the end, you have about 5e5+2*max_radius vectors, having a total of maximum n*2*max_radius intervals. Now for each vector containing intervals, you need to calculate the number of points that at least one interval covers, which is pretty easy to do, just make two events for [l,r] segment, (l,+1) and (r,-1), sort by first value, and a simple prefix sum over second values should do the job, when it becomes 0 you count the points you've encountered so far.

Hi n00bie, Thanks for taking the time to help me out. Can you please explain the last part of your solution?

This one -

"Now for each vector containing intervals, you need to calculate the number of points that at least one interval covers, which is pretty easy to do, just make two events for [l,r] segment, (l,+1) and (r,-1), sort by first value, and a simple prefix sum over second values should do the job, when it becomes 0 you count the points you've encountered so far."

Sure. After all the steps, you're left with this problem — given a bunch of intervals [l,r], find the number of points that are covered by at least one interval.

Each interval kind of denotes 2 events, one is its starting time and other its ending time. If you sort those events for all intervals while keeping track of if it's start event or end event, you have chronological order of the events happening. Let's keep +1 and -1 paired with time of event for denoting start and end of interval.

Now, if you maintain a prefix sum of the +1/-1 values while going over the events in increasing order of time, you'll notice that it's either positive or zero. When it's positive, that means the points you saw from last event to this event were part of some interval, otherwise the prefix sum would have been 0. So, you simply add the number of points between these two events, and then update prefix sum with current event. If the prefix sum is 0, then you don't count, because no interval covered the points between current and last event. In either case, you first check the prefix sum till previous event, update final answer, then update prefix sum with current event.

This is a pretty standard thing to do while doing problems on intervals, though I don't know what it's called.

Thanks for sharing this problem, I found it very interesting :)

I could only think of a

O(n*R*log(C+R) +C), whereCis the biggest coordinate value andRis the biggest radius value.The idea is to use a scanline approach (imagine a vertical line moving horizontally in every point on the x-axis). While doing so, we will maintain a set of "active circles", which are the circles that the line is currently intersecting. Maintaining the set can be done in

O(C+R) using some buckets in which we'll store event "add circle" in indexX_{i}-R_{i}and event "remove circle" in indexX_{i}+R_{i}.Now, at each

xcoordinate, we will need to count number of integer points we are currently standing on.We can do this in

O(n*logC) by iterating on each active circle and adding some interval of points covered at givenxto either a set of`pair<int,int>`

or a segment tree. To compute this interval, you need to simply find the 2ycoordinate of the circle at the givenx.This might look

O(C*n*logC), which is too much, but it's actually not as each circle can be "active" for at most 2 *R+ 1 coordinates, which means that for each circle we will do at mostO(R) add-interval operations, which result in the complexity ofO(C+n*R*logC).Note that it should be possible in the vertical scan-line approach for each distinct radius

Rto compute in the integer intervalUnable to parse markup [type=CF_TEX]

the functionNote also that

Y_{max}(x+ 1,R) ≤Y_{max}(x,R) for 0 ≤x≤R- 1, and thatY_{max}(1,R) =R- 1 for anyR. Therefore,Y_{max}(x,R) is a non-increasing function ofxfor the sameR.The integer vertical interval for which the scan line

x=x_{s}, where |x_{s}-x_{c}| ≤R, is inside a circle with center (x_{c},y_{c}) and radiusRcan be expressed as|

y-y_{c}| ≤Y_{max}(|x_{s}-x_{c}|,R)This may reduce the Execution Time when several circles have the same large radius

R, asY_{max}(x,R) can be computed and stored for each distinct radiusRin a dynamic-programming sense, and used subsequently by the scan-line approach.The following is a simple C++ data structure to pre-compute

Y_{max}(x,R) for a distinctRand store theR+ 1 integer values for 0 ≤x≤Rin an inherited`vector<int>`

base object.