Intersect
Турнир за Купата на Декана, 2011
Time Limit: 0.1s, Memory Limit: 64MiB
Ели започна да пише първата си компютърна игра. В нея космически корабчета се обстрелват в 2D пространството със специални снаряди, които се движат по права линия и с времето стават по-големи (можете да си ги представите като разширяващи се кръгове, чиито център се движи по права линия). Когато някой от снарядите уцели базата на противника, на екрана се изписва "All your base are belong to us" и играта приключва.

Ели не е сигурна дали е написала правилно модула, който проверява пресичането на снаряд с права, затова моли вас да й помогнете. Правата се задава чрез две различни точки по нея. Снарядът на i-тия кораб бива изстрелян от точката (Xi, Yi), като изминава DXi единици по абсцисата и DYi единици по ординатата и разширява радиуса си с DRi за единица време. Всички снаряди биват изстреляни едновременно във време нула, като първоначално имат радиус близък до нула.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя снаряди. На следващите N реда ще бъдат зададени по пет цели числа Xi, Yi, DXi, DYi, DRi – информацията за всеки от снарядите. На последния ред на входа ще бъдат зададени четири цели числа LX1, LY1, LX2, LY2 – две точки по правата, с която Ели иска да пресече снарядите. Гарантирано е, че тези две точки няма да съвпадат, както и че няма да има кораб, който да лежи на правата.
Изход
На стандартния изход изведете едно реално число – времето до първото пресичане на снаряд с правата. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9. Ако никой от снарядите никога не пресича линията, вместо това изведете "NEVER".
Ограничения
  • 1 ≤ N ≤ 1,000
  • 0 ≤ DRi ≤ 10,000
  • -10,000 ≤ Xi, Yi, DXi, DYi, LX1, LY1, LX2, LY2 ≤ 10,000
Примерен Вход Примерен Изход
2 1 9 0 -3 2 4 1 -1 1 1 1 3 3 4 1.145898034
1 1 1 1 1 1 0 0 1 -1 NEVER
3 42 42 13 17 3 2 42 1 -4 2 113 117 -1 -2 7 1 -1 -1 1 7.549206511
За пресичане се счита дори докосване, тоест ако правата се явява допирателна на някоя от окръжностите. Снарядите могат да се разминават помежду си.
Мрън!