HouseProtection
SRM 397 · 2008-04-12 · by mateuszek
Problem Statement
You have recently started to feel unsafe in your own house, so you decided to place surveillance radars in the garden. When a radar with range r is placed at point S, it totally covers the area of the circle with radius r centered at point S. The maximum allowable range is R, and all your radars must be set to the same range.
There are two types of radars - blue and red. You can buy as many of each as you like, but they can only be placed at certain points in the garden. You are given two
Your goal is to place the radars in such a way that maximizes the safety factor. The safety factor is the sum of all the areas covered by the radars. Note that if an area is covered by multiple radars, it will count multiple times toward the sum. Return the maximal safety factor you can achieve.
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
- possibleXForBlue will contain between 1 and 50 elements, inclusive.
- possibleXForBlue and possibleYForBlue will both contain the same number of elements.
- Each element of possibleXForBlue will be between -1000 and 1000, inclusive.
- Each element of possibleYForBlue will be between -1000 and 1000, inclusive.
- All points represented by possibleXForBlue and possibleYForBlue will be distinct.
- possibleXForRed will contain between 1 and 50 elements, inclusive.
- possibleXForRed and possibleYForRed will both contain the same number of elements.
- Each element of possibleXForRed will be between -1000 and 1000, inclusive.
- Each element of possibleYForRed will be between -1000 and 1000, inclusive.
- All points represented by possibleXForRed and possibleYForRed will be distinct.
- R will be between 1 and 1000, inclusive.
{ 0, 4 }
{ 0, 0 }
{ 2, 1 }
{ 2, -1 }
1
Returns: 9.42477796076938
We can place two blue radars at points (0,0) and (4,0) and one red radar at point (2,2). Setting their ranges to 1 will give us the safety factor of about 3.14 * 3 = 9.42.
{ 1 }
{ 1 }
{ 1 }
{ 1 }
5
Returns: 78.53981633974483
Note that there may be overlap between the allowable points for blue radars and the allowable points for red radars.
{ 12, 32, 13, 43, 13, 43 }
{ 32, 21, 32, 21, 11, 5 }
{ 43, 54, 23, 56, 12, 13 }
{ 13, 43, 22, 11, 14, 19 }
801
Returns: 1.209389392881519E7
{ 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150 }
{ 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150 }
{ 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150 }
{ 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150 }
1000
Returns: 1.5707963267948964E8
{ 0, 8 }
{ 0, 0 }
{ 4, 4 }
{ 3, -3 }
3
Returns: 78.53981633974483
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HouseProtection with a public method double safetyFactor(vector<int> possibleXForBlue, vector<int> possibleYForBlue, vector<int> possibleXForRed, vector<int> possibleYForRed, int R) · 123 test cases · 2 s / 256 MB per case