Flight Control |
An air traffic controller has access to the following information for each aircraft on the screen:
Each aircraft begins its journey at the position (x1, y1, z1) and then, it directly flies in a straight line at constant speed from (x1, y1, z1) to (x2, y2, z2), ..., from (xk-1, yk-1, zk-1) to (xk, yk, zk), and finally from (xk, yk, zk) to (0, 0, 0), where each position is relative to the head of the track. After the aircraft arrives at the head of the track, it disappears from the controller's screen.
On a day-to-day basis, air traffic controllers deal with conflict detection and resolution. Therefore, for an air traffic controller is very important to have an alarm system to indicate the specific points where it must take corrective actions to prevent accidents.
It is noteworthy that, geometrically speaking, a conflict warning occurs when the security spheres of two
aircrafts touch. Formally, a conflict warning begins when two aircrafts approach at a distance less than or equal to
the sum of the radius of their security spheres, is maintained while this condition is satisfied, and ends when their security
spheres stop touching (i.e., when the distance between both is greater than the sum of the radius of their security spheres).
Distances are measured with an acceptable error threshold
> 0.
Despite years of effort and the billions of dollars that have been spent on computer software designed to assist air
traffic control, success has been largely limited to improving the tools at the disposal of the controllers. However, today you
have the chance to improve the impact of computer software in the air traffic control world.
You have been hired by the International Center of Planning Control (ICPC) to determine the quality of the
traffic routes defined by the Aircraft Controller Management (ACM), through the measurement of the number of dangerous
situations that should fix the air traffic controller. Your task is to write a program that, given the information of two aircrafts,
determines the number of different conflict warnings that would arise if both aircrafts follow the scheduled route starting at the
same time and finishing at the track's head.
The first line of the input contains the number of test cases. Each test case specifies the information of the two studied aircrafts, where each aircraft is described as follows:
For each route, you may assume that either xi xi+1, yi yi+1 or zi zi+1 for all 1 i < k, and that either xk 0, yk 0 or zk 0. The acceptable error threshold is = 10-10 meters.
For each test, print one line informing the number of different conflict warnings.
7 20 300 2 10000 1000 5000 1000 100 500 20 100 3 10000 1000 2000 1000 100 500 100 0 0 20 300 2 0 10000 5000 0 -10000 5000 20 300 3 10000 0 5010 -10000 0 5010 -8000 1000 3010 20 300 2 0 10000 5000 0 -10000 5000 20 300 2 10000 0 5010 -10000 0 5010 25 200 2 3000 6000 3000 4000 5000 3000 25 200 2 3000 6000 3005 4000 5000 3005 20 300 2 5000 4000 3000 4000 5000 3000 20 300 2 3000 6000 3005 4000 5000 3005 10 100 1 -1000 0 0 10 100 2 1000 21 0 -1000 21 0 10 100 1 -1000 0 0 10 100 2 1000 20 0 -1000 20 0
0 1 2 1 1 0 1