Connection Status:
Competition Arena > CityRebuild

CityRebuild

TCO 2014 Celebrity Match · 2014-03-26 · by dreamoon

TCO 2014 Celebrity Match · 2014-03-26 · by dreamoon · Geometry, Graph Theory
Class Name: CityRebuild
Return Type: double
Method Name: maximumSideLength
Arg Types: (int, int, vector<int>, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CityRebuild with a public method double maximumSideLength(int W, int H, vector<int> x, vector<int> y) · 92 test cases · 2 s / 256 MB per case

Submitting as anonymous