RadioRange
SRM 621 · 2013-12-22 · by rng_58
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
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
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.
{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.
{-28}
{-49}
{7}
965
Returns: 0.9854922279792746
{-187730043, 932334096, 59236807, -602044448, 441157147, 569003535, 563472630, 493784941, -928345136, -198534684, -507361726, -486699261, -705601684, -671249417, -79879427, 71698248, 146683444, 414416326, 53196305, -666818573, 178619454, -893182413, 224302710, 296990194, -885921154, -173521881, -493092068, 900325848, -353242967, -631482448, 112982750, 553248219, 264762102, -318102799, -836641673, -812311860, -73259832, 609869565, 650010687, 155243096, -107417345, 634247427, -841502473, -651719520, -958664893, 480384188, -691415372, 36346544, 706329659, 126652235, 44403422, -263265167, -349491074, 120258505, 485027199, -240466308, -456782932, 192953958, -261803363, -198063552, 980391799, 997148607, 417112854, -333017353, -945493557, 371446553, 251150037, -960076588, -360362805, -305175580, 208353048, -437834549, -420355623, -668454094, 180494692, 755143595, 249998094, 537726369, 343336414, 495586169, 35446018, 131243302, 501744441, 739753520, -876687692, 560013605, -443087342, 455209428, 333669368, 398118304, -695213876, 527566904, -463103162, -317355625, 641069703, -947785900, -532490870, -963111776, -727898154, 748858912}
{452827103, 247175647, 11753377, -611873763, -531081305, 859586805, -868286674, -876539858, 304963335, 990345765, -859353631, -475065113, -574709927, 131112520, -846074893, 464742988, -41360301, 899849149, -266820064, -251052777, 226747686, 876712903, -350309643, 131456902, -799664596, 453822371, -617483392, 755895436, -72097080, 199834107, -619495741, -922106677, 229012084, 419002428, 38711443, 293733516, 633211140, -65526196, -776215532, -491310115, -23818472, 792447417, 726536324, -686011537, -140383515, -569321731, -402939093, -125768005, -18416939, 127783325, -67341991, -322587512, -296995968, -536590267, 437613161, -206640690, -825549222, 102733497, -399947312, 55751657, 527107031, -152726436, -821534503, 267030010, -528297582, -897079824, -521362885, 1225411, 460297398, 596603062, -270748768, 211858545, -654848212, -353416243, 955853430, -447642704, 739273996, -118039293, 583896289, -253276293, 632398992, 560349797, 222539806, 677153439, -804423594, -285780470, 782032960, 23986706, -812231058, 344193048, 491603558, 956077657, -97237599, -644202406, -311702606, 645844112, 47834815, -802896183, 472801824, 658244534}
{4, 7, 4, 4, 5, 1, 8, 4, 5, 7, 8, 3, 5, 5, 9, 5, 8, 5, 6, 7, 7, 8, 10, 6, 10, 6, 3, 4, 5, 1, 5, 8, 9, 8, 2, 3, 1, 9, 8, 5, 8, 6, 9, 2, 2, 9, 9, 2, 6, 4, 8, 2, 4, 9, 7, 5, 5, 2, 1, 9, 2, 5, 6, 10, 4, 9, 4, 4, 10, 1, 10, 9, 8, 10, 2, 2, 9, 10, 3, 4, 6, 10, 5, 1, 9, 3, 5, 5, 4, 5, 5, 5, 1, 10, 6, 7, 1, 1, 10, 2}
1000000000
Returns: 0.999999094
{39, -8, 30, -78}
{-22, -85, 70, 27}
{5, 4, 10, 8}
118
Returns: 0.7086172212326564
{-30, -56, 11, 13, -16}
{84, 44, 61, -72, -45}
{2, 10, 4, 5, 10}
423
Returns: 0.8883354458869681
{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.
{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.
{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].
{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.
Submissions are judged against all 140 archived test cases, of which 9 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RadioRange with a public method double RadiusProbability(vector<int> X, vector<int> Y, vector<int> R, int Z) · 140 test cases · 2 s / 256 MB per case