TopCoder problem "HouseProtection" used in SRM 397 (Division I Level Three)



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 int[]s possibleXForBlue and possibleYForBlue, where (possibleXForBlue[i], possibleYForBlue[i]) is the i-th point where you are allowed to place a blue radar. Similarly, you are given two int[]s possibleXForRed and possibleYForRed describing the allowable points for red radars. You cannot place more than one radar at a single point. Also, the area covered by blue radars cannot overlap with the area covered by red radars. Otherwise, the whole system will malfunction.



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.

 

Definition

    
Class:HouseProtection
Method:safetyFactor
Parameters:int[], int[], int[], int[], int
Returns:double
Method signature:double safetyFactor(int[] possibleXForBlue, int[] possibleYForBlue, int[] possibleXForRed, int[] possibleYForRed, int R)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
{ 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 }
{ 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.
2)
    
{ 0 }
{ 0 }
{ 100 }
{ 0 }
51
Returns: 15707.963267948966
3)
    
{ 23, 29, 29, 35 }
{ 77, 79, 75, 77 }
{ 26, 26, 32 }
{ 78, 76, 76 }
3
Returns: 113.09733552923255

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8762

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12169&pm=8762

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Geometry, Graph Theory, Search, Simple Math