JOIN
Get Time

   Problem Statement  

 Problem Statement for RadioRange

Problem Statement

    

Note that the return value is a floating-point number and that in this problem the allowed absolute or relative error has been increased to 1e-6.



This problem takes place in a plane. Nikola works at a radio station that is located in the point (0, 0). You can hear the station if and only if you are within a circle with center at (0, 0) and some unknown radius.



There are some cities near the station. Each city has the shape of a circle with some positive integer radius. Cities may partially or even completely overlap each other, and some of them may contain the radio station. You are given the description of all cities as int[]s X, Y, and R. For each valid i, there is a city with center at (X[i], Y[i]) and radius R[i].



The radius of our radio station is bad if there is a city that is only partially covered by the radio signal. Otherwise, the radius is good. In other words, if there is a point in a city where you can listen to our radio and another point in the same city where you cannot do so, the radius is bad. A radius is good if and only if each city is either covered completely by radio signal, or not covered at all.



You are given a int Z. The radius of our radio station is a real number chosen uniformly at random from the range [0, Z]. Return the probability that the radius is good.

 

Definition

    
Class:RadioRange
Method:RadiusProbability
Parameters:int[], int[], int[], int
Returns:double
Method signature:double RadiusProbability(int[] X, int[] Y, int[] R, int Z)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-6.
 

Constraints

-X will contain between 1 and 100 elements, inclusive.
-X, Y, and R will each contain the same number of elements.
-Each element of X will be between -10^9 and 10^9, inclusive.
-Each element of Y will be between -10^9 and 10^9, inclusive.
-Each element of R will be between 1 and 10^9, inclusive.
-Z will be between 1 and 10^9, inclusive.
 

Examples

0)
    
{0}
{0}
{5}
10
Returns: 0.5
Our radio station is in the center of a city with radius 5, and we are choosing the radius for the station uniformly at random from [0,10]. Radii in [0,5) are all bad, because people in the center of the city can hear our radio but people on its boundary cannot. Radii in [5,10] are all good, as the entire city is covered. Hence, the probability of having a good radius is 5/10 = 0.5.
1)
    
{0}
{0}
{10}
10
Returns: 0.0
Our radio station is in the center of a city with radius 10, and we are choosing the radius for the station uniformly at random from [0,10]. In this case, the only good radius is 10, but the probability that it will be chosen is zero.
2)
    
{10}
{10}
{10}
10
Returns: 0.4142135623730951
The center of the city is at (10, 10) and its radius is 10. The good radii for our station are those where the city is not covered at all. These are the radii from 0 to approximately 4.14.
3)
    
{11, -11, 0, 0}
{0, 0, 11, -11}
{10, 10, 10, 10}
31
Returns: 0.3548387096774194
Here we have four cities. They are located to the north, south, east, and west of the station. A radius is good if it lies in [0,1) or in [21,31].
4)
    
{100}
{100}
{1}
10
Returns: 1.0
It is possible that some cities will not be covered even if the radius of our radio station is Z.
5)
    
{1000000000}
{1000000000}
{1000000000}
1000000000
Returns: 0.41421356237309503
6)
    
{20, -20, 0, 0}
{0, 0, 20, -20}
{50, 50, 50, 50}
100
Returns: 0.3
7)
    
{0, -60, -62, -60, 63, -97}
{-72, 67, 61, -8, -32, 89}
{6, 7, 8, 7, 5, 6}
918
Returns: 0.9407071068962471

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 621 Round 1 - Division I, Level One