ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1600. Airport

Time limit: 1.0 second
Memory limit: 64 MB
A new system for preventing airplane collisions is installed at the Koltsovo airport. The system traces all flying objects within a certain radius of action: airplanes, helicopters, parachutists, etc. It is assumed that objects move in straight lines with constant speeds, and their motions are calculated according to this model. If the distance between two objects becomes equal to some critical value d, the system gives an alarm. You are given coordinates and velocities of objects. Determine the pair that will first cause an alarm.


In the first line you are given the number n (at most 500) of objects within the range of the system and the critical distance d (from 0.1 to 10000). Each of the following n lines contains the current coordinates (x, y, z) and the velocity components (vx, vy, vz) of a flying object. The absolute values of coordinates do not exceed 10000, and the absolute values of velocity do not exceed 100. At the initial moment, the objects are at safe distances from each other.


If there will be an alarm, then output "ALARM!" in the first line. The second line must contain the time t of the first alarm (up to the third fractional digit) and the numbers of the objects at the critical distance from each other at that moment a and b; the initial time moment is 0. If at the moment t there are several pairs of objects at the critical distance, then output any of them. The objects are enumerated from 1 to n in the order in which they are given in the input. If there are no alarms, output "OK".


2 1.0
1.0 1.0 -1.0 0.0 0.0 10.0
0.0 0.0 4.0 2.0 0.0 0.0
0.500 1 2
Problem Author: Vladimir Yakovlev
Problem Source: IX USU Open Personal Contest (March 1, 2008)