eolymp
bolt
Try our new interface for solving problems
Problems

Collision Detection

Collision Detection

Time limit 1 second
Memory limit 64 MiB

As a preliminary step in developing an autonomous vehicle system, your team is seeking to prove that a central traffic controller can sound an alert when automobiles are likely to collide unless corrective actions are taken.

The test course consists of a number of straight tracks that intersect at a variety of angles. As cars pass sensors mounted on the tracks, their position and speed is recorded and sent to the central controller. The controller remembers its two most recent sets of readings for each car. We want the controller to sound the alert whenever two cars will, if they behave as predicted, pass 'dangerously close' to one another any time within the next 30 seconds (following the most recent of the sensor readings). For this purpose, consider that cars are dangerously close if they pass within 18ft. of one another. Cars are considered safe if their closest approach is at least 20ft apart. A passage within 18ft to 20ft is considered ambiguous.

Assume that

  • The cars remain on their straight course

  • The acceleration (change in speed per unit time) of each car remains constant over the time between observations and for the next 30 sec, with the two exceptions given below.

    • Exception 1: if the car is decelerating, it stops decelerating if its speed reaches zero (cars do not shift into reverse).

    • Exception 2: if the car is accelerating, it stops accelerating if its speed reaches 80 feet per second (about55 MPH).

Given the two most recent sets of reading for each of two cars, determine if they will pass within 18ft of each other within 30 seconds of the last measurement.

Input data

There will be multiple test cases in the input. Each test case consists of four observations, one observation per line. The first two observations are for the first car, the second two observations are for the second car.

Each observation consists of four floating point numbers t, x, y and s, separated by single spaces, where:

  • t is the time of the observation in seconds (0t120)

  • x and y give the position of the car at the time of the observation, in feet (-5000x, y5000)

  • s is the speed in feet per second (0s80)

There will be no data sets in which the closest approach within the indicated timer interval falls in the ambiguous 18ft to 20ft. range. The two observations for a given car will always occur at distinct times, and the first time for each car will be before the second time for that car.

Input is terminated with a line with four negative numbers.

Output data

For each data set, print a single line consisting of either 1 if the cars will come within 18 feet of each other within 30 seconds following the maximum of the 4 input times, or 0 if not. Output no extra spaces, and do not separate answers with blank lines.

Examples

Input example #1
10 0 0 10
11 7.42 7.42 11
11 41.0 106.0 16
12 56 106 14
0 0 0 50
0.5 21.7 12.5 50.1
0.25 39.0 22.5 50
0.75 60.7 35.0 50.1
-1 -1 -1 -1
Output example #1
1
0