CityRebuild | Topcoder Archive

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

```
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.
```
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.
```
100
```
```
100
```
```
{100}
```
```
{100}
```
```
Returns: 0.0
```

{20,40,60,80}

{50,50,50,50}

Returns: 40.0

```
100
```
```
100
```
```
{50,50}
```
```
{50,50}
```
```
Returns: 100.0
```
```
100
```
```
100
```
```
{50,50,50}
```
```
{50,50,50}
```
```
Returns: 0.0
```
```
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)2024, Topcoder, Inc. All rights reserved.