Problem Statement |
| |
Batman is assigning the night surveillance activities for himself and Robin. Batman will assign a convex area of the plane to himself, and another convex area to Robin. To avoid jurisdictional problems, assigned areas must not intersect or touch each other. The surveilled area is then the union of the area surveilled by Batman and the area surveilled by Robin. There are several conflictive points in the city that need to be patrolled, so the assignment Batman will do needs to make sure all those points lay within the surveilled area or on its boundary.
Night surveillance is a very time and power consuming task. The power needed by either Batman or Robin to do the surveillance of a given area, measured in bat-units, is exactly the surface of the area. Batman is very lazy and wants to consume the minimum of his own power, but he does not care about Robin's consumption. However, since he is the most experienced and the leader of the team, and in order to keep Robin from suspecting he is lazy, he never assigns to Robin an area strictly larger than the area he assigns to himself.
You will be given the set of conflictive points in two integer arrays. The X coordinate of conflictive point i will be given by element i of x, and the Y coordinate by element i of y. Return the minimum power Batman will need for a night of surveillance if he optimizes the assignment of the areas.
|
| |
Definition |
| | | Class: | BatmanAndRobin | | Method: | minArea | | Parameters: | int[], int[] | | Returns: | double | | Method signature: | double minArea(int[] x, int[] y) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A convex area is a set S of points in the plane such that if two points belong to S, the segment that connects them is fully contained in S. |
| - | The returned value must have an absolute or relative error less than 1e-9. |
| |
Constraints |
| - | x and y will contain the same number of elements. |
| - | The number of elements in x will be between 1 and 50, inclusive. |
| - | Each element of x and y will be between -1000 and 1000, inclusive. |
| - | Each represented point will be different. |
| |
Examples |
| 0) | |
| | {100,100,90,90,-100,-100,-90,-90} | {100,90,100,90,-100,-90,-100,-90} |
| Returns: 100.0 | | This area can be partitioned into two small squares of size 100. |
|
|
| 1) | |
| | {-1000,-1000,1000,1000,1000,-1000} | {-1000,1000,-1000,1000,0,0} |
| Returns: 0.0 | | Both Batman and Robin can be assigned an area as small as Batman wants and still cover the necessary points. |
|
|
| 2) | |
| | {-1000,-1000,1000,1000,0} | {-1000,1000,-1000,1000,0} |
| Returns: 1000000.0 | | Note that areas cannot overlap, and Batman gets stuck with the center point while Robin has a minimal surveillance area. |
|
|
| 3) | |
| | {-904,-812,-763,-735,-692,-614,-602,-563,-435,-243,-87,-52,-28,121,126,149,157,185,315,336,390,470,528,591,673,798,815,837,853,874} | {786,10,-144,949,37,-857,-446,-969,-861,-712,5,-972,-3,-202,-845,559,-244,-542,-421,422,526,-501,-791,-899,-315,281,-275,467,743,-321} |
| Returns: 1067472.0 | |
|