[1994 ACM finals problem set | My ACM problem archive | my home page]

Monitoring Wheelchair Patients

A map of the restricted area is shown. The restricted area is a 200 ft by 400 ft rectangular area of the lawn. Patients enter the restricted area from the door of a building located on the southern edge of the restricted area. The door is at the center of the 400 ft southern boundary, as shown in the figure.

The recording device turns itself on when the patient enters the restricted area through the door and monitors the patient's movements for up to 1 hour. Time is measured in seconds from 0 to 3600, with time 0 being the time the patient initially enters the restricted area through the door. The device records 4 numbers to describe the motion of the wheelchair during any interval when the motor is in operation. The first two numbers give the time the motion begins and ends; the third number gives the speed during the time interval; and the fourth number gives the compass bearing during the time interval. (During each time interval the wheelchair maintains constant speed and bearing.) For example, the recorded line

10.6 15.9 2.8 274would indicate that between times t

Your job is to analyze the data from the wheelchair's recording device. Specifically, you must determine the following:

- Did the patient ever leave the restricted area? If so, determine the first time that the patient left the restricted area and determine at what point on the perimeter of the restricted area the wheelchair crossed out of the restricted area. If the patient did not leave the restricted area, what was the distance from the door to the farthest point the patient reached within the area?
- What was the total distance that the patient traveled?

In the first data set of the sample input, the patient entered through the door (at time 0.0) and for the first 5 seconds was traveling due north at 3 ft/sec. From time t = 7 to t = 9 he traveled at a speed of 2 ft/sec with a compass bearing of 30°. He then stopped, changed his bearing to 60°, and then traveled at 4 ft/sec from time t = 10 to time t = 100. Ten seconds later (at time t = 110) he headed due north at 2 ft/sec until t = 200.

4 0.0 5.0 3.0 0 7.0 9.0 2.0 30 10.0 100.0 4.0 60 110.0 200.0 2.0 0 3 0.0 20.0 2.0 0 500.0 600.0 1.0 270 3000.0 3100.0 1.0 0 7 0.0 5.3 2.1 0 19.8 35.6 2.7 346 42.0 78.4 2.3 15 1181.4 1192.1 1.7 117 2107.0 2193.6 2.1 295 2196.3 2201.2 2.0 298 2704.3 2709.2 1.5 208 0

Case Number 1 Left restricted area at point (400.0,132.8) and time 67.2 sec. Total distance traveled was 559.0 feet *************************************** Case Number 2 No departure from restricted area Maximum distance patient traveled from door was 172.0 feet Total distance traveled was 240.0 feet *************************************** Case Number 3 Left restricted area at point (67.0,200.0) and time 2191.4 sec. Total distance traveled was 354.7 feet ***************************************

*
Assumptions and requirements
*

- Within each data set, time intervals will be listed in chronological order, with the first time interval always having time 0.0 as the time of entry into the restricted area. All times will be given with one decimal place accuracy and will be in the range 0.0 to 3600.0 inclusive. For each time interval specified, the duration of the time interval will be positive, i.e. the second time specified will be greater than the first.
- Speeds will be in the range 0.1 to 9.9 ft/sec.
- Compass bearings will be given as a whole number of degrees and will be in the range 0 to 359 inclusive. The initial compass bearing for the first line of data in each data set will be 0.
- Within each line of data, numbers will be separated by at least one blank space.
- All numerical results will be displayed with one decimal place of accuracy as shown in the sample output.
- If the patient goes out of the restricted area, his location may include negative coordinates. However, you don't have to worry about the wheelchair crashing through the walls of the building.

This page maintained by Ed Karrels.

Last updated September 20, 1999