TopCoder / SRM 621 Div1 250

During SRM 621 I solved only 250 problem, but after the contest I figured out the solution to 500 which I'm going to write about in the next post. Now let's focus on 250 problem.

250 Problem

You're given a N \leq 100 circles on the plane and the integer 1 \leq Z \leq 10^9. The i-th circle has a center in (x_i, y_i) and a radius r_i, where x_i, y_i \in [-10^9, 10^9] and 1 \leq r_i \leq 10^9. A special circle has to be placed with a center in (0, 0) and a radius R chosen uniformly at random from an interval [0, Z]. We say that the special circle is good when there is no other circle which intersects with the special circle, in other words all points lying within any regular circle has to be either inside or outside the special circle. Your task is to compute the probability that the special circle is good. Let's consider an example input:

 

circles1

 

A very basic but a crucial observation is that for any regular circle it doesn't matter what's the relative position of that circle. Only the radius and the distance from it's center to (0, 0) matter. So we can transform the problem from 3D to 2D which is always good.

Let d_i be the distance from the center of the i-th circle to (0, 0). Then the i-th circle corresponds to a segment [d_i - r_i, d_i + r_i] and choosing R corresponds to choosing a point from [0, Z]. The above example corresponds to the following picture:

 

circles2

 

For a given Z, we're interested in segments in R which lies in any [a, b] where 0 \leq a \leq b \leq Z and [a, b] doesn't intersect with any regular circle. For our example, the good segments are marked green in the following picture:

 

circles3

 

Now, it's easy to see that the probability we're looking for equals 1 - X / Z, where X is the length of a sum of segments corresponding to the regular circles limited to [0, Z]. We can compute X easily by sorting the segments and then process these segments one by one and count the amount of space where at least one segment is open. If you're interested, I'm putting my code below:

double dist(int x, int y)
{
    return sqrt(pow(x, 2) + pow(y, 2));
}

class RadioRange {
    public:
    double RadiusProbability(vector X, vector Y, vector R, int Z) {
        vector > v;
        FOR(i, X.size())
        {
            double d = dist(X[i], Y[i]);
            v.pb(mp(max(d - R[i], 0.0), 0));
            v.pb(mp(d + R[i], 1));
        }
        sort(ALL(v));
        int open = 0;
        double checkpoint = 0.0;
        double res = 0.0;
        FOR(i, v.size())
        {
            double d = v[i].fi;
            if(d > Z) break;
            if(v[i].se == 0)
            {
                if(open == 0)
                {
                    checkpoint = d;
                }
                open++;
            }
            else
            {
                open--;
                if(open == 0)
                {
                    res += d - checkpoint;
                }
            }
        }
        if(open > 0)
        {
            res += Z - checkpoint;
        }
        return 1 - res / Z;
    }
};