Connection Status:
Competition Arena > Alarmed

Alarmed

TCO07 Qual 1 · 2007-03-07 · by dgoodman

TCO07 Qual 1 · 2007-03-07 · by dgoodman · Geometry, Search
Class Name: Alarmed
Return Type: double
Method Name: noise
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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!

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
4)
{ 1,99}
{ 50,50}
{ 10, 20}
Returns: 32955.71787875179

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

Coding Area

Language: C++17 · define a public class Alarmed with a public method double noise(vector<int> x, vector<int> y, vector<int> threshold) · 61 test cases · 2 s / 256 MB per case

Submitting as anonymous