SecretSuperstar's blog

By SecretSuperstar, history, 10 days ago, In English,

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 <= 5e5

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.

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

»
10 days ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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."

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

»
8 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

I could only think of a O(n * R * log(C + R) + C), where C is the biggest coordinate value and R is 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 index Xi - Ri and event "remove circle" in index Xi + Ri.

Now, at each x coordinate, 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 given x to either a set of pair<int,int> or a segment tree. To compute this interval, you need to simply find the 2 y coordinate of the circle at the given x.

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 most O(R) add-interval operations, which result in the complexity of O(C + n * R * logC).

»
8 days ago, # |
Rev. 17   Vote: I like it +5 Vote: I do not like it

Note that it should be possible in the vertical scan-line approach for each distinct radius R to compute in the integer interval the function

Note also that Ymax(x + 1, R) ≤ Ymax(x, R) for 0 ≤ x ≤ R - 1, and that Ymax(1, R) = R - 1 for any R. Therefore, Ymax(x, R) is a non-increasing function of x for the same R.

The integer vertical interval for which the scan line x = xs, where |xs - xc| ≤ R, is inside a circle with center (xc, yc) and radius R can be expressed as

|y - yc| ≤ Ymax(|xs - xc|, R)

This may reduce the Execution Time when several circles have the same large radius R, as Ymax(x, R) can be computed and stored for each distinct radius R in a dynamic-programming sense, and used subsequently by the scan-line approach.

The following is a simple C++ data structure to pre-compute Ymax(x, R) for a distinct R and store the R + 1 integer values for 0 ≤ x ≤ R in an inherited vector<int> base object.

struct Ymax_t: vector< int >
{
    Ymax_t( int R )
    {
        push_back( R ); // Y_max(0,R) = R

        for( long double r = R, y2 = r * r - 1, x = 1; x < R; y2 -= 2 * x + 1, x++ )
            push_back( sqrt( y2 ) );

        push_back( 0 ); // Y_max(R,R) = 0
    }
};