JOIN
Get Time

   Problem Statement  

 Problem Statement for CityRebuild

Problem Statement

    

This problem has a non-standard time limit: 4 seconds.

Dirty City is so dirty that the mayor of Dirty City wants to rebuild it. Dirty City has n buildings. You are given two int[]s x, y and two ints H, W. The center of the i-th building is located at (x[i], y[i]). Dirty City has a rectangular shape with four corners at (0,0), (W,0), (W,H), (0,H) in a Cartesian coordinate system.

The mayor of Dirty City wants all the buildings to have a shape of isosceles right triangle. The following properties must hold for each of the buildings:

  • A building center must be exactly in the middle of triangle hypotenuse.
  • A triangle hypotenuse should be parallel to one of the axis.
  • All hypotenuses must have the same length.
  • All buildings must be inside the Dirty City rectangle.
  • Buildings must not overlap.

Please help the mayor of Dirty City to rebuild the buildings. Return the maximal possible hypotenuse length.

 

Definition

    
Class:CityRebuild
Method:maximumSideLength
Parameters:int, int, int[], int[]
Returns:double
Method signature:double maximumSideLength(int W, int H, int[] x, int[] y)
(be sure your method is public)
    
 

Notes

-We consider two buildings are overlapping when their overlapping area is greater than 0.
-Two building's center may locate on same coordinate.
-Your return value must have an absolute or a relative error at most 1e-9.
 

Constraints

-W and H should be between 1 and 1,000,000,000(10^9), inclusive.
-The number of elements of x and y should be the same.
-The number of elements of x shoulde between 1 and 60, inclusive.
-All elements of x should be between 0 and W, inclusive.
-All elements of y should be between 0 and H, inclusive.
 

Examples

0)
    
10
10
{5}
{5}
Returns: 10.0

You can rebuild the only building in isosceles right triangle shape (0,5)-(5,0)-(10,5) and the length of hypotenuse is 10.

1)
    
100
100
{5,5,0,10}
{0,10,5,5}
Returns: 10.0

The four buildings can be rebuilded to shapes (0,0)-(5,5)-(0,10), (0,10)-(5,5)-(10,10), (0,0)-(5,5)-(10,0), and (0,10)-(5,5)-(10,10), respectively.

2)
    
100
100
{100}
{100}
Returns: 0.0
3)
    
100
100
{20,40,60,80}
{50,50,50,50}
Returns: 40.0
4)
    
100
100
{50,50}
{50,50}
Returns: 100.0
5)
    
100
100
{50,50,50}
{50,50,50}
Returns: 0.0
6)
    
1000
20
{100}
{13}
Returns: 26.0

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:
       2014 TCO Algorithm Celebrity Match - Division I, Level Three