TopCoder problem "Alarmed" used in TCO07 Qual 1 (Division I Level Three)



Problem Statement

    Our alarm system is intended to keep intruders from entering at the front door of a square room, crossing the room, and then exiting through the back door. It consists of noise sensors located at various points on the floor of the room. Each sensor has its own threshold sound level -- it will warn us if the sound level at the sensor exceeeds its threshold.

The sound generated by an intruder attenuates according to an inverse square law. Specifically, at a distance r from an intruder, the sound level will be A/r2, where A is the noisiness of the intruder.

The room is square, with each side of length 100.0. The coordinates of the southwest corner are (x=0,y=0) and the coordinates of the northeast corner are (x=100,y=100). The intruder will enter at (50,0) and exit at (50,100).

Given int[]s x, y, and threshold return the largest value of A that will allow an intruder to walk through the room without setting off an alarm. The i-th sensor is described by the ith elements of x, y, and threshold. Note that we cannot expect an intruder to limit his path to integer coordinates!

 

Definition

    
Class:Alarmed
Method:noise
Parameters:int[], int[], int[]
Returns:double
Method signature:double noise(int[] x, int[] y, int[] threshold)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
 

Constraints

-x will contain between 1 and 50 elements, inclusive.
-x, y and threshold will contain the same number of elements.
-All sensor locations will be distinct.
-Each element of x and y will be between 1 and 99, inclusive.
-Each element of threshold will be between 1 and 10,000, inclusive.
 

Examples

0)
    
{50}
{2}
{87}
Returns: 347.99999999999994
Here there is one sensor, very close to the front door. The intruder can move along the wall where he enters and continue to follow the walls until he gets to the exit door. The closest he will get to the one sensor is at the point where he enters the room which is a distance of 2 away. If A is 348 the alarm will not sound, since 348/(2*2), the largest sound level at the sensor, does not exceed the threshold of the sensor, but any bigger value of A will sound the alarm.
1)
    
{1,99}
{50,50}
{1,1}
Returns: 2400.9999999999995
There are two very sensitive sensors located near the east wall and the west wall. The best path for an intruder is straight through the room. Then the closest he will get to a sensor is a distance of 49, and the crucial value of A will be 49*49 = 2401.0.
2)
    
{3,11,2,62,91}
{90,10,75,25,50}
{5,4,3,2,1}
Returns: 1537.9999999999998
3)
    
{ 1,99}
{ 50,50}
{ 1, 2}
Returns: 3295.5717878751793

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10730&pm=7479

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , legakis , Olexiy

Problem categories:

Geometry, Search